From: adam Date: Thu, 8 Jul 2004 09:57:20 +0000 (+0000) Subject: initial import X-Git-Url: http://git.megacz.com/?p=org.ibex.util.git;a=commitdiff_plain;h=3a85dab61cef1346315ca40d3004f8772815127f initial import darcs-hash:20040708095720-5007d-2b67e7821cb1e0bea6cd1abd47783e2b0ec6b62e.gz --- 3a85dab61cef1346315ca40d3004f8772815127f diff --git a/src/org/ibex/util/AccessibleCharArrayWriter.java b/src/org/ibex/util/AccessibleCharArrayWriter.java new file mode 100644 index 0000000..62e436a --- /dev/null +++ b/src/org/ibex/util/AccessibleCharArrayWriter.java @@ -0,0 +1,9 @@ +package org.ibex.util; + +import java.io.*; + +public class AccessibleCharArrayWriter extends CharArrayWriter { + public char[] getBuf() { return buf; } + public AccessibleCharArrayWriter(int i) { super(i); } +} + diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java new file mode 100644 index 0000000..82226c2 --- /dev/null +++ b/src/org/ibex/util/BalancedTree.java @@ -0,0 +1,410 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +// FEATURE: private void intersection() { } +// FEATURE: private void union() { } +// FEATURE: private void subset() { } +// FEATURE: grow if we run out of slots + +/** a weight-balanced tree with fake leaves */ +public class BalancedTree { + + + // Instance Variables /////////////////////////////////////////////////////////////////// + + private int root = 0; ///< the slot of the root element + + private int cached_index = -1; + private int cached_slot = -1; + + // Public API ////////////////////////////////////////////////////////////////////////// + + /** the number of elements in the tree */ + public final int treeSize() { + synchronized(BalancedTree.class) { + return root == 0 ? 0 : size[root]; + } + } + + /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */ + public final void insertNode(int index, Object o) { + synchronized(BalancedTree.class) { + if(o == null) throw new Error("can't insert nulls in the balanced tree"); + cached_slot = cached_index = -1; + if (index < 0) index = 0; + if (index > treeSize()) index = treeSize(); + int arg = allocateSlot(o); + if (root != 0) { + insert(index, arg, root, 0, false, false); + } else { + root = arg; + left[arg] = right[arg] = parent[arg] = 0; + size[arg] = 1; + } + } + } + + /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */ + public final void replaceNode(int index, Object o) { + synchronized(BalancedTree.class) { + if(o == null) throw new Error("can't insert nulls in the balanced tree"); + cached_slot = cached_index = -1; + if(root == 0) throw new Error("called replaceNode() on an empty tree"); + if (index < 0) index = 0; + if (index >= treeSize()) index = treeSize() - 1; + int arg = allocateSlot(o); + insert(index, arg, root, 0, true, false); + } + } + + /** returns the index of o; runs in O((log n)^2) time unless cache hit */ + public final int indexNode(Object o) { + synchronized(BalancedTree.class) { + if(o == null) return -1; + if (cached_slot != -1 && objects[cached_slot] == o) return cached_index; + + int slot = getSlot(o); + if(slot == -1) return -1; + + int index = 0; + while(true) { + // everything to the left is before us so add that to the index + index += sizeof(left[slot]); + // we are before anything on the right + while(left[parent[slot]] == slot) slot = parent[slot]; + // we end of the first node who isn't on the left, go to the node that has as its child + slot = parent[slot]; + // if we just processed the root we're done + if(slot == 0) break; + // count the node we're currently on towards the index + index++; + } + return index; + } + } + + /** returns the object at index; runs in O(log n) time unless cache hit */ + public final Object getNode(int index) { + synchronized(BalancedTree.class) { + if (index == cached_index) return objects[cached_slot]; + + if (cached_index != -1) { + int distance = Math.abs(index - cached_index); + // if the in-order distance between the cached node and the + // target node is less than log(n), it's probably faster to + // search directly. + if ((distance < 16) && ((2 << distance) < treeSize())) { + while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; } + while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; } + return objects[cached_slot]; + } + } + /* + cached_index = index; + cached_slot = get(index, root); + return objects[cached_slot]; + */ + return objects[get(index, root)]; + } + } + + /** deletes the object at index, returning the deleted object */ + public final Object deleteNode(int index) { + synchronized(BalancedTree.class) { + cached_slot = cached_index = -1; + // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children + int del = delete(index, root, 0); + left[del] = right[del] = size[del] = parent[del] = 0; + Object ret = objects[del]; + objects[del] = null; + return ret; + } + } + + public final void clear() { + synchronized(BalancedTree.class) { + if(root == 0) return; + int i = leftmost(root); + do { + int next = next(i); + objects[i] = null; + left[i] = right[i] = size[i] = parent[i] = 0; + i = next; + } while(i != 0); + root = 0; + } + } + + protected void finalize() { clear(); } + + + // Node Data ///////////////////////////////////////////////////////////////////////// + + private final static int NUM_SLOTS = 64 * 1024; + // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32; + + /** + * Every object inserted into *any* tree gets a "slot" in this + * array. The slot is determined by hashcode modulo the length of + * the array, with quadradic probing to resolve collisions. NOTE + * that the "slot" of a node is NOT the same as its index. + * Furthermore, if an object is inserted into multiple trees, that + * object will have multiple slots. + */ + private static Object[] objects = new Object[NUM_SLOTS]; + + /// These two arrays hold the left and right children of each + /// slot; in other words, left[x] is the *slot* of the left child + /// of the node in slot x. + /// + /// If x has no left child, then left[x] is -1 multiplied by the + /// slot of the node that precedes x; if x is the first node, then + /// left[x] is 0. The right[] array works the same way. + /// + private static int[] left = new int[NUM_SLOTS]; + private static int[] right = new int[NUM_SLOTS]; + + /// The parent of this node (0 if it is the root node) + private static int[] parent = new int[NUM_SLOTS]; + + ///< the number of descendants of this node *including the node itself* + private static int[] size = new int[NUM_SLOTS]; + + + // Slot Management ////////////////////////////////////////////////////////////////////// + + /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */ + private int getSlot(Object o, boolean alloc) { + // we XOR with our own hashcode so that we don't get tons of + // collisions when a single Object is inserted into multiple + // trees + int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length; + Object search = alloc ? null : o; + int odest = dest; + boolean plus = true; + int tries = 1; + if(dest == 0) dest=1; + while (objects[dest] != search || !(alloc || root(dest) == root)) { + dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length); + if (dest == 0) dest=1; + if (plus) tries++; + plus = !plus; + // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1; + } + return dest; + } + + /** returns the slots holding object o */ + private int getSlot(Object o) { return getSlot(o,false); } + + /** allocates a new slot holding object o*/ + private int allocateSlot(Object o) { + int slot = getSlot(o, true); + // FEATURE: GROW - if(slot == -1) throw new Error("out of slots"); + objects[slot] = o; + return slot; + } + + + + // Helpers ///////////////////////////////////////////////////////////////////////// + + private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); } + private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); } + private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); } + private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); } + private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; } + private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); } + + + // Rotation and Balancing ///////////////////////////////////////////////////////////// + + // p p + // | | + // b d + // / \ / \ + // a d < == > b e + // / \ / \ + // c e a c + // FIXME might be doing too much work here + private void rotate(boolean toTheLeft, int b, int p) { + int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right; + int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left; + int d = right[b]; + int c = left[d]; + if (d <= 0) throw new Error("rotation error"); + left[d] = b; + right[b] = c <= 0 ? -d : c; + + parent[b] = d; + parent[d] = p; + if(c > 0) parent[c] = b; + if (p == 0) root = d; + else if (left[p] == b) left[p] = d; + else if (right[p] == b) right[p] = d; + else throw new Error("rotate called with invalid parent"); + size[b] = 1 + sizeof(left[b]) + sizeof(right[b]); + size[d] = 1 + sizeof(left[d]) + sizeof(right[d]); + } + + private void balance(int slot, int p) { + if (slot <= 0) return; + size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]); + if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p); + else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p); + } + + + + // Insert ///////////////////////////////////////////////////////////////////////// + + private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) { + int diff = slot <= 0 ? 0 : index - sizeof(left[slot]); + if (slot > 0 && diff != 0) { + if (diff < 0) insert(index, arg, left[slot], slot, replace, true); + else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false); + balance(slot, p); + return; + } + + if (size[arg] != 0) throw new Error("double insertion"); + + // we are replacing an existing node + if (replace) { + if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index + if (p == 0) root = arg; + else if (left[p] == slot) left[p] = arg; + else if (right[p] == slot) right[p] = arg; + left[arg] = left[slot]; + right[arg] = right[slot]; + size[arg] = size[slot]; + parent[arg] = parent[slot]; + if(left[slot] > 0) parent[left[slot]] = arg; + if(right[slot] > 0) parent[right[slot]] = arg; + objects[slot] = null; + left[slot] = right[slot] = size[slot] = parent[slot] = 0; + + // we become the child of a former leaf + } else if (slot <= 0) { + int[] left = wentLeft ? BalancedTree.left : BalancedTree.right; + int[] right = wentLeft ? BalancedTree.right : BalancedTree.left; + left[arg] = slot; + left[p] = arg; + right[arg] = -1 * p; + parent[arg] = p; + balance(arg, p); + + // we take the place of a preexisting node + } else { + left[arg] = left[slot]; // steal slot's left subtree + left[slot] = -1 * arg; + right[arg] = slot; // make slot our right subtree + parent[arg] = parent[slot]; + parent[slot] = arg; + if (slot == root) { + root = arg; + balance(slot, arg); + balance(arg, 0); + } else { + if (left[p] == slot) left[p] = arg; + else if (right[p] == slot) right[p] = arg; + else throw new Error("should never happen"); + balance(slot, arg); + balance(arg, p); + } + } + } + + + // Retrieval ////////////////////////////////////////////////////////////////////// + + private int get(int index, int slot) { + int diff = index - sizeof(left[slot]); + if (diff > 0) return get(diff - 1, right[slot]); + else if (diff < 0) return get(index, left[slot]); + else return slot; + } + + + // Deletion ////////////////////////////////////////////////////////////////////// + + private int delete(int index, int slot, int p) { + int diff = index - sizeof(left[slot]); + if (diff < 0) { + int ret = delete(index, left[slot], slot); + balance(slot, p); + return ret; + + } else if (diff > 0) { + int ret = delete(diff - 1, right[slot], slot); + balance(slot, p); + return ret; + + // we found the node to delete + } else { + + // fast path: it has no children + if (left[slot] <= 0 && right[slot] <= 0) { + if (p == 0) root = 0; + else { + int[] side = left[p] == slot ? left : right; + side[p] = side[slot]; // fix parent's pointer + } + + // fast path: it has no left child, so we replace it with its right child + } else if (left[slot] <= 0) { + if (p == 0) root = right[slot]; + else (left[p] == slot ? left : right)[p] = right[slot]; // fix parent's pointer + parent[right[slot]] = p; + left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr + balance(right[slot], p); + + // fast path; it has no right child, so we replace it with its left child + } else if (right[slot] <= 0) { + if (p == 0) root = left[slot]; + else (left[p] == slot ? left : right)[p] = left[slot]; // fix parent's pointer + parent[left[slot]] = p; + right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr + balance(left[slot], p); + + // node to be deleted has two children, so we replace it with its left child's rightmost descendant + } else { + int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot); + left[left_childs_rightmost] = left[slot]; + right[left_childs_rightmost] = right[slot]; + if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost; + if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost; + parent[left_childs_rightmost] = parent[slot]; + if (p == 0) root = left_childs_rightmost; + else (left[p] == slot ? left : right)[p] = left_childs_rightmost; // fix parent's pointer + balance(left_childs_rightmost, p); + } + + return slot; + } + } + + // Debugging /////////////////////////////////////////////////////////////////////////// + + public void printTree() { + if(root == 0) System.err.println("Tree is empty"); + else printTree(root,0,false); + } + private void printTree(int node,int indent,boolean l) { + for(int i=0;i all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +import java.io.*; +import java.util.*; +import java.util.zip.*; + +/** Reads a CAB file structure */ +public class CAB { + + /** reads a CAB file, parses it, and returns an InputStream representing the named file */ + public static InputStream getFileInputStream(InputStream is, String fileName) throws IOException, EOFException { + return getFileInputStream(is, 0, fileName); + } + + public static InputStream getFileInputStream(InputStream is, int skipHeaders, String fileName) throws IOException, EOFException { + DataInputStream dis = new DataInputStream(is); + CFHEADER h = new CFHEADER(); + + while (skipHeaders > 0) { CFHEADER.seekMSCF(dis); skipHeaders--; } + + try { + h.read(dis); + } catch (CFHEADER.BogusHeaderException bhe) { + throw new EOFException(); + } + + for(int i=0; i limit) len = limit; + if (limit == 0) return -1; + int ret = super.read(b, off, len); + limit -= ret; + return ret; + } + } + + /** Encapsulates a CFHEADER entry */ + public static class CFHEADER { + byte[] reserved1 = new byte[4]; // reserved + int fileSize = 0; // size of this cabinet file in bytes + byte[] reserved2 = new byte[4]; // reserved + int offsetOfFirstCFFILEEntry; // offset of the first CFFILE entry + byte[] reserved3 = new byte[4]; // reserved + byte versionMinor = 3; // cabinet file format version, minor + byte versionMajor = 1; // cabinet file format version, major + boolean prevCAB = false; // true iff there is a cabinet before this one in a sequence + boolean nextCAB = false; // true iff there is a cabinet after this one in a sequence + boolean hasReserved = false; // true iff the cab has per-{cabinet, folder, block} reserved areas + int setID = 0; // must be the same for all cabinets in a set + int indexInCabinetSet = 0; // number of this cabinet file in a set + byte perCFFOLDERReservedSize = 0; // (optional) size of per-folder reserved area + byte perDatablockReservedSize = 0; // (optional) size of per-datablock reserved area + byte[] perCabinetReservedArea = null; // per-cabinet reserved area + String previousCabinet = null; // name of previous cabinet file in a set + String previousDisk = null; // name of previous disk in a set + String nextCabinet = null; // name of next cabinet in a set + String nextDisk = null; // name of next disk in a set + + CFFOLDER[] folders = new CFFOLDER[0]; + CFFILE[] files = new CFFILE[0]; + + int readCFFOLDERs = 0; // the number of folders read in so far + int readCFFILEs = 0; // the number of folders read in so far + + public void print(PrintStream ps) { + ps.println("CAB CFFILE CFHEADER v" + ((int)versionMajor) + "." + ((int)versionMinor)); + ps.println(" total file size = " + fileSize); + ps.println(" offset of first file = " + offsetOfFirstCFFILEEntry); + ps.println(" total folders = " + folders.length); + ps.println(" total files = " + files.length); + ps.println(" flags = 0x" + + Integer.toString((prevCAB ? 0x1 : 0x0) | + (nextCAB ? 0x2 : 0x0) | + (hasReserved ? 0x4 : 0x0), 16) + " [ " + + (prevCAB ? "prev " : "") + + (nextCAB ? "next " : "") + + (hasReserved ? "reserve_present " : "") + "]"); + ps.println(" set id = " + setID); + ps.println(" index in set = " + indexInCabinetSet); + ps.println(" header reserved area #1 =" + + " 0x" + Integer.toString(reserved1[0], 16) + + " 0x" + Integer.toString(reserved1[1], 16) + + " 0x" + Integer.toString(reserved1[2], 16) + + " 0x" + Integer.toString(reserved1[3], 16)); + ps.println(" header reserved area #2 =" + + " 0x" + Integer.toString(reserved2[0], 16) + + " 0x" + Integer.toString(reserved2[1], 16) + + " 0x" + Integer.toString(reserved2[2], 16) + + " 0x" + Integer.toString(reserved2[3], 16)); + ps.println(" header reserved area #3 =" + + " 0x" + Integer.toString(reserved3[0], 16) + + " 0x" + Integer.toString(reserved3[1], 16) + + " 0x" + Integer.toString(reserved3[2], 16) + + " 0x" + Integer.toString(reserved3[3], 16)); + if (hasReserved) { + if (perCabinetReservedArea != null) { + ps.print(" per-cabinet reserved area = "); + for(int i=0; i 0) + dis.readFully(perCabinetReservedArea); + } + + try { + if (prevCAB) { + previousCabinet = readZeroTerminatedString(dis); + previousDisk = readZeroTerminatedString(dis); + } + if (nextCAB) { + nextCabinet = readZeroTerminatedString(dis); + nextDisk = readZeroTerminatedString(dis); + } + } catch (ArrayIndexOutOfBoundsException e) { + throw new BogusHeaderException(); + } + } + + public static void seekMSCF(DataInputStream dis) throws EOFException, IOException + { + int state; + // skip up to and including the 'MSCF' signature + state = 0; + while (state != 4) { + // M + while (state == 0 && dis.readByte() != 0x4D) { } + state = 1; + // S + switch (dis.readByte()) { + case 0x53 : state = 2; break; + case 0x4D : state = 1; continue; + default : state = 0; continue; + } + // C + if (dis.readByte() == 0x43) { state = 3; } + else { state = 0; continue; } + // F + if (dis.readByte() == 0x46) { state = 4; } + else { state = 0; } + } + } + + public static class BogusHeaderException extends IOException {} + } + + /** Encapsulates a CFFOLDER entry */ + public static class CFFOLDER { + public static final int COMPRESSION_NONE = 0; + public static final int COMPRESSION_MSZIP = 1; + public static final int COMPRESSION_QUANTUM = 2; + public static final int COMPRESSION_LZX = 3; + + int firstBlockOffset = 0; // offset of first data block within this folder + int numBlocks = 0; // number of data blocks + int compressionType = 0; // compression type for this folder + byte[] reservedArea = null; // per-folder reserved area + int indexInCFHEADER = 0; // our index in CFHEADER.folders + Vector files = new Vector(); + + private CFHEADER header = null; + + public CFFOLDER(CFHEADER header) { this.header = header; } + + public String toString() { + return "[ CAB CFFOLDER, " + numBlocks + " data blocks, compression type " + + compressionName(compressionType) + + ", " + reservedArea.length + " bytes of reserved data ]"; + } + + public void read(DataInputStream dis) throws IOException, UnsupportedCompressionTypeException { + firstBlockOffset = readLittleInt(dis); + numBlocks = readLittleShort(dis); + compressionType = readLittleShort(dis) & 0x000F; + if (compressionType != COMPRESSION_MSZIP) { + throw new UnsupportedCompressionTypeException(compressionType); + } + reservedArea = new byte[header.perCFFOLDERReservedSize]; + if (reservedArea.length > 0) dis.readFully(reservedArea); + indexInCFHEADER = header.readCFFOLDERs++; + header.folders[indexInCFHEADER] = this; + } + + public static String compressionName(int type) { + switch (type) { + case COMPRESSION_NONE: + return "NONE"; + case COMPRESSION_MSZIP: + return "MSZIP"; + case COMPRESSION_QUANTUM: + return "QUANTUM"; + case COMPRESSION_LZX: + return "LZX"; + default: + return ""; + } + } + + public static class UnsupportedCompressionTypeException extends IOException { + private int compressionType; + + UnsupportedCompressionTypeException(int type) { + compressionType = type; + } + public String toString() { + return "UnsupportedCompressionTypeException: no support for compression type " + compressionName(compressionType); + } + } + } + + /** Encapsulates a CFFILE entry */ + public static class CFFILE { + int fileSize = 0; // size of this file + int uncompressedOffsetInCFFOLDER = 0; // offset of this file within the folder, not accounting for compression + int folderIndex = 0; // index of the CFFOLDER we belong to + Date date = null; // modification date + int attrs = 0; // attrs + boolean readOnly = false; // read-only flag + boolean hidden = false; // hidden flag + boolean system = false; // system flag + boolean arch = false; // archive flag + boolean runAfterExec = false; // true if file should be run during extraction + boolean UTFfileName = false; // true if filename is UTF-encoded + String fileName = null; // filename + int indexInCFHEADER = 0; // our index in CFHEADER.files + CFFOLDER folder = null; // the folder we belong to + private CFHEADER header = null; + File myFile; + + public CFFILE(CFHEADER header) { this.header = header; } + + public CFFILE(File f, String pathName) throws IOException { + fileSize = (int)f.length(); + folderIndex = 0; + date = new java.util.Date(f.lastModified()); + fileName = pathName; + myFile = f; + } + + public String toString() { + return "[ CAB CFFILE: " + fileName + ", " + fileSize + " bytes [ " + + (readOnly ? "readonly " : "") + + (system ? "system " : "") + + (hidden ? "hidden " : "") + + (arch ? "arch " : "") + + (runAfterExec ? "run_after_exec " : "") + + (UTFfileName ? "UTF_filename " : "") + + "]"; + } + + public void read(DataInputStream dis) throws IOException { + fileSize = readLittleInt(dis); + uncompressedOffsetInCFFOLDER = readLittleInt(dis); + folderIndex = readLittleShort(dis); + readLittleShort(dis); // date + readLittleShort(dis); // time + attrs = readLittleShort(dis); + readOnly = (attrs & 0x1) != 0; + hidden = (attrs & 0x2) != 0; + system = (attrs & 0x4) != 0; + arch = (attrs & 0x20) != 0; + runAfterExec = (attrs & 0x40) != 0; + UTFfileName = (attrs & 0x80) != 0; + fileName = readZeroTerminatedString(dis); + + indexInCFHEADER = header.readCFFILEs++; + header.files[indexInCFHEADER] = this; + folder = header.folders[folderIndex]; + folder.files.addElement(this); + } + } + + + + + // Compressing Input and Output Streams /////////////////////////////////////////////// + + /** an InputStream that decodes CFDATA blocks belonging to a CFFOLDER */ + private static class CFFOLDERInputStream extends InputStream { + CFFOLDER folder; + DataInputStream dis; + InputStream iis = null; + + byte[] compressed = new byte[128 * 1024]; + byte[] uncompressed = new byte[256 * 1024]; + + public CFFOLDERInputStream(CFFOLDER f, DataInputStream dis) { + this.folder = f; + this.dis = dis; + } + + InputStream readBlock() throws IOException { + int compressedBytes = readLittleShort(dis); + int unCompressedBytes = readLittleShort(dis); + byte[] reserved = new byte[/*folder.header.perDatablockReservedSize*/0]; + if (reserved.length > 0) dis.readFully(reserved); + if (dis.readByte() != 0x43) throw new CABException("malformed block header"); + if (dis.readByte() != 0x4B) throw new CABException("malformed block header"); + + dis.readFully(compressed, 0, compressedBytes - 2); + + Inflater i = new Inflater(true); + i.setInput(compressed, 0, compressedBytes - 2); + + if (unCompressedBytes > uncompressed.length) uncompressed = new byte[unCompressedBytes]; + try { i.inflate(uncompressed, 0, uncompressed.length); + } catch (DataFormatException dfe) { + dfe.printStackTrace(); + throw new CABException(dfe.toString()); + } + return new ByteArrayInputStream(uncompressed, 0, unCompressedBytes); + } + + public int available() throws IOException { return iis == null ? 0 : iis.available(); } + public void close() throws IOException { iis.close(); } + public void mark(int i) { } + public boolean markSupported() { return false; } + public void reset() { } + + public long skip(long l) throws IOException { + if (iis == null) iis = readBlock(); + int ret = 0; + while (l > ret) { + long numread = iis.skip(l - ret); + if (numread == 0 || numread == -1) iis = readBlock(); + else ret += numread; + } + return ret; + } + + public int read(byte[] b, int off, int len) throws IOException { + if (iis == null) iis = readBlock(); + int ret = 0; + while (len > ret) { + int numread = iis.read(b, off + ret, len - ret); + if (numread == 0 || numread == -1) iis = readBlock(); + else ret += numread; + } + return ret; + } + + public int read() throws IOException { + if (iis == null) iis = readBlock(); + int ret = iis.read(); + if (ret == -1) { + iis = readBlock(); + ret = iis.read(); + } + return ret; + } + } + + + + // Misc Stuff ////////////////////////////////////////////////////////////// + + public static String readZeroTerminatedString(DataInputStream dis) throws IOException { + int numBytes = 0; + byte[] b = new byte[256]; + while(true) { + byte next = dis.readByte(); + if (next == 0x0) return new String(b, 0, numBytes); + b[numBytes++] = next; + } + } + + public static int readLittleInt(DataInputStream dis) throws IOException { + int lowest = (int)(dis.readByte() & 0xff); + int low = (int)(dis.readByte() & 0xff); + int high = (int)(dis.readByte() & 0xff); + int highest = (int)(dis.readByte() & 0xff); + return (highest << 24) | (high << 16) | (low << 8) | lowest; + } + + public static int readLittleShort(DataInputStream dis) throws IOException { + int low = (int)(dis.readByte() & 0xff); + int high = (int)(dis.readByte() & 0xff); + return (high << 8) | low; + } + + public static class CABException extends IOException { + public CABException(String s) { super(s); } + } + + + /** scratch space for isToByteArray() */ + static byte[] workspace = new byte[16 * 1024]; + + /** Trivial method to completely read an InputStream */ + public static synchronized byte[] isToByteArray(InputStream is) throws IOException { + int pos = 0; + while (true) { + int numread = is.read(workspace, pos, workspace.length - pos); + if (numread == -1) break; + else if (pos + numread < workspace.length) pos += numread; + else { + pos += numread; + byte[] temp = new byte[workspace.length * 2]; + System.arraycopy(workspace, 0, temp, 0, workspace.length); + workspace = temp; + } + } + byte[] ret = new byte[pos]; + System.arraycopy(workspace, 0, ret, 0, pos); + return ret; + } + + +} + diff --git a/src/org/ibex/util/Cache.java b/src/org/ibex/util/Cache.java new file mode 100644 index 0000000..af88c88 --- /dev/null +++ b/src/org/ibex/util/Cache.java @@ -0,0 +1,126 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +/* + +Bug report from a user: + +I looked at your Cache.java and tried to make good use of it, but I was +out of luck - it wouldn't run here. Digging deeper into the code, I came +across something that might be considered a bug. But maybe it's just a +feature :-) + + +Starting with an empty cache, Cache.put() immediately followed by +Cache.get() on same keys / same object will set Node lru back to null in +Node.remove() which is called in get(). + +Assuming this put()-get() sequence is fixed, it will fill the cache, but +lru will remain null. + +When cache is filled 100%, we have, at the end of the get(), where +size>maxSize is checked, a state that mru == lru == n (from +if(lru==null) thus deleteting the newly inserted object. Oops. + + +Hope I made this clear enough. Maybe it's not a problem in xwt due to a +different usage scheme of the cache. + + + +*/ + +package org.ibex.util; + +// FIXME needs to be a weak hash + +/** + * A Hash table with a fixed size; drops extraneous elements. Uses + * LRU strategy. + */ +public class Cache extends Hash { + + /** head of list is the mru; tail is the lru */ + Node mru = null; + Node lru = null; + + private int maxSize; + private Cache() { } + public Cache(int maxSize) { + super(maxSize * 2, 3); + this.maxSize = maxSize; + } + + /** A doubly-linked list */ + private class Node { + final Object val; + final Object k1; + final Object k2; + public Node(Object k1, Object k2, Object val) { this.k1 = k1; this.k2 = k2; this.val = val; } + Node next = null; + Node prev = null; + void remove() { + if (this == lru) lru = prev; + if (this == mru) mru = next; + if (next != null) next.prev = prev; + if (prev != null) prev.next = next; + next = prev = null; + } + void placeAfter(Node n) { + remove(); + if (n == null) return; + next = n.next; + if (n.next != null) n.next.prev = this; + n.next = this; + prev = n; + } + void placeBefore(Node n) { + remove(); + if (n == null) return; + next = n; + prev = n.prev; + n.prev = this; + if (prev != null) prev.next = this; + } + } + + public void clear() { + lru = null; + super.clear(); + } + + public void remove(Object k1, Object k2) { + Object o = super.get(k1, k2); + if (o != null) ((Node)o).remove(); + super.remove(k1, k2); + } + + public Object get(Object k1, Object k2) { + Node n = (Node)super.get(k1, k2); + if (n == null) return null; + n.remove(); + n.placeBefore(mru); + mru = n; + return n.val; + } + + public void put(Object k1, Object k2, Object v) { + Node n = new Node(k1, k2, v); + if (lru == null) { + lru = mru = n; + } else { + n.placeBefore(mru); + mru = n; + } + if (super.get(k1, k2) != null) remove(k1, k2); + super.put(k1, k2, n); + if (size > maxSize) remove(lru.k1, lru.k2); + } + +} + + diff --git a/src/org/ibex/util/CachedInputStream.java b/src/org/ibex/util/CachedInputStream.java new file mode 100644 index 0000000..a712f84 --- /dev/null +++ b/src/org/ibex/util/CachedInputStream.java @@ -0,0 +1,88 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; +import java.io.*; + +// FEATURE: don't use a byte[] if we have a diskCache file +/** + * Wraps around an InputStream, caching the stream in a byte[] as it + * is read and permitting multiple simultaneous readers + */ +public class CachedInputStream { + + boolean filling = false; ///< true iff some thread is blocked on us waiting for input + boolean eof = false; ///< true iff end of stream has been reached + byte[] cache = new byte[1024 * 128]; + int size = 0; + final InputStream is; + File diskCache; + + public CachedInputStream(InputStream is) { this(is, null); } + public CachedInputStream(InputStream is, File diskCache) { + this.is = is; + this.diskCache = diskCache; + } + public InputStream getInputStream() throws IOException { + if (diskCache != null && diskCache.exists()) return new FileInputStream(diskCache); + return new SubStream(); + } + + public void grow(int newLength) { + if (newLength < cache.length) return; + byte[] newCache = new byte[cache.length + 2 * (newLength - cache.length)]; + System.arraycopy(cache, 0, newCache, 0, size); + cache = newCache; + } + + synchronized void fillCache(int howMuch) throws IOException { + if (filling) { try { wait(); } catch (InterruptedException e) { }; return; } + filling = true; + grow(size + howMuch); + int ret = is.read(cache, size, howMuch); + if (ret == -1) { + eof = true; + // FIXME: probably a race here + if (diskCache != null && !diskCache.exists()) + try { + File cacheFile = new File(diskCache + ".incomplete"); + FileOutputStream cacheFileStream = new FileOutputStream(cacheFile); + cacheFileStream.write(cache, 0, size); + cacheFileStream.close(); + cacheFile.renameTo(diskCache); + } catch (IOException e) { + Log.info(this, "exception thrown while writing disk cache"); + Log.info(this, e); + } + } + else size += ret; + filling = false; + notifyAll(); + } + + private class SubStream extends InputStream implements KnownLength { + int pos = 0; + public int available() { return Math.max(0, size - pos); } + public long skip(long n) throws IOException { pos += (int)n; return n; } // FEATURE: don't skip past EOF + public int getLength() { return eof ? size : is instanceof KnownLength ? ((KnownLength)is).getLength() : 0; } + public int read() throws IOException { // FEATURE: be smarter here + byte[] b = new byte[1]; + int ret = read(b, 0, 1); + return ret == -1 ? -1 : b[0]&0xff; + } + public int read(byte[] b, int off, int len) throws IOException { + synchronized(CachedInputStream.this) { + while (pos >= size && !eof) fillCache(pos + len - size); + if (eof && pos == size) return -1; + int count = Math.min(size - pos, len); + System.arraycopy(cache, pos, b, off, count); + pos += count; + return count; + } + } + } +} diff --git a/src/org/ibex/util/Callback.java b/src/org/ibex/util/Callback.java new file mode 100644 index 0000000..471df9b --- /dev/null +++ b/src/org/ibex/util/Callback.java @@ -0,0 +1,15 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +/** a simple interface for callbacks*/ +public interface Callback { + + public abstract Object call(Object arg); + +} diff --git a/src/org/ibex/util/CounterEnumeration.java b/src/org/ibex/util/CounterEnumeration.java new file mode 100644 index 0000000..5a01f3e --- /dev/null +++ b/src/org/ibex/util/CounterEnumeration.java @@ -0,0 +1,17 @@ +// Copyright (C) 2004 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") +package org.ibex.util; +import java.util.*; + +public class CounterEnumeration implements Enumeration { + public final int max; + private int cur = 0; + public CounterEnumeration(int i) { max = i; } + public void reset() { cur = 0; } + public boolean hasMoreElements() { return cur < max; } + public Object nextElement() { return new Integer(cur++); } +} diff --git a/src/org/ibex/util/DirtyList.java b/src/org/ibex/util/DirtyList.java new file mode 100644 index 0000000..0a77a94 --- /dev/null +++ b/src/org/ibex/util/DirtyList.java @@ -0,0 +1,181 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +/** + * A general-purpose data structure for holding a list of rectangular + * regions that need to be repainted, with intelligent coalescing. + * + * DirtyList will unify two regions A and B if the smallest rectangle + * enclosing both A and B occupies no more than epsilon + Area_A + + * Area_B. Failing this, if two corners of A fall within B, A will be + * shrunk to exclude the union of A and B. + */ +public class DirtyList { + + /** The dirty regions (each one is an int[4]). */ + private int[][] dirties = new int[10][]; + + /** The number of dirty regions */ + private int numdirties = 0; + + /** See class comment */ + private static final int epsilon = 50 * 50; + + public int num() { return numdirties; } + + /** grows the array */ + private void grow() { + int[][] newdirties = new int[dirties.length * 2][]; + System.arraycopy(dirties, 0, newdirties, 0, numdirties); + dirties = newdirties; + } + + /** Add a new rectangle to the dirty list; returns false if the + * region fell completely within an existing rectangle or set of + * rectangles (ie did not expand the dirty area) + */ + public synchronized boolean dirty(int x, int y, int w, int h) { + if (numdirties == dirties.length) grow(); + + // we attempt the "lossless" combinations first + for(int i=0; i= cur[0] && y >= cur[1] && x + w <= cur[0] + cur[2] && y + h <= cur[1] + cur[3]) { + return false; + + // existing region falls completely within new region + } else if (x <= cur[0] && y <= cur[1] && x + w >= cur[0] + cur[2] && y + h >= cur[1] + cur[3]) { + dirties[i][2] = 0; + dirties[i][3] = 0; + + // left end of new region falls within existing region + } else if (x >= cur[0] && x < cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) { + w = x + w - (cur[0] + cur[2]); + x = cur[0] + cur[2]; + i = -1; continue; + + // right end of new region falls within existing region + } else if (x + w > cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) { + w = cur[0] - x; + i = -1; continue; + + // top end of new region falls within existing region + } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y < cur[1] + cur[3]) { + h = y + h - (cur[1] + cur[3]); + y = cur[1] + cur[3]; + i = -1; continue; + + // bottom end of new region falls within existing region + } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y + h > cur[1] && y + h <= cur[1] + cur[3]) { + h = cur[1] - y; + i = -1; continue; + + // left end of existing region falls within new region + } else if (dirties[i][0] >= x && dirties[i][0] < x + w && dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) { + dirties[i][2] = dirties[i][2] - (x + w - dirties[i][0]); + dirties[i][0] = x + w; + i = -1; continue; + + // right end of existing region falls within new region + } else if (dirties[i][0] + dirties[i][2] > x && dirties[i][0] + dirties[i][2] <= x + w && + dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) { + dirties[i][2] = x - dirties[i][0]; + i = -1; continue; + + // top end of existing region falls within new region + } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && dirties[i][1] >= y && dirties[i][1] < y + h) { + dirties[i][3] = dirties[i][3] - (y + h - dirties[i][1]); + dirties[i][1] = y + h; + i = -1; continue; + + // bottom end of existing region falls within new region + } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && + dirties[i][1] + dirties[i][3] > y && dirties[i][1] + dirties[i][3] <= y + h) { + dirties[i][3] = y - dirties[i][1]; + i = -1; continue; + } + + } + + // then we attempt the "lossy" combinations + for(int i=0; i 0 && h > 0 && cur[2] > 0 && cur[3] > 0 && + ((max(x + w, cur[0] + cur[2]) - min(x, cur[0])) * + (max(y + h, cur[1] + cur[3]) - min(y, cur[1])) < + w * h + cur[2] * cur[3] + epsilon)) { + int a = min(cur[0], x); + int b = min(cur[1], y); + int c = max(x + w, cur[0] + cur[2]) - min(cur[0], x); + int d = max(y + h, cur[1] + cur[3]) - min(cur[1], y); + dirties[i][2] = 0; + dirties[i][3] = 0; + return dirty(a, b, c, d); + } + } + + dirties[numdirties++] = new int[] { x, y, w, h }; + return true; + } + + /** Returns true if there are no regions that need repainting */ + public boolean empty() { return (numdirties == 0); } + + /** + * Atomically returns the list of dirty rectangles as an array of + * four-int arrays and clears the internal dirty-rectangle + * list. Note that some of the regions returned may be null, or + * may have zero height or zero width, and do not need to be + * repainted. + */ + public synchronized int[][] flush() { + if (numdirties == 0) return null; + int[][] ret = dirties; + for(int i=numdirties; ib) return a; + else return b; + } + + /** included here so that it can be inlined */ + private static final int min(int a, int b, int c) { + if (a<=b && a<=c) return a; + else if (b<=c && b<=a) return b; + else return c; + } + + /** included here so that it can be inlined */ + private static final int max(int a, int b, int c) { + if (a>=b && a>=c) return a; + else if (b>=c && b>=a) return b; + else return c; + } + + /** included here so that it can be inlined */ + private static final int bound(int a, int b, int c) { + if (a > b) return a; + if (c < b) return c; + return b; + } + +} diff --git a/src/org/ibex/util/EjAlbertBrowserLauncher.java b/src/org/ibex/util/EjAlbertBrowserLauncher.java new file mode 100644 index 0000000..cf46138 --- /dev/null +++ b/src/org/ibex/util/EjAlbertBrowserLauncher.java @@ -0,0 +1,589 @@ +package org.ibex.util; + +import java.io.File; +import java.io.IOException; +import java.lang.reflect.Constructor; +import java.lang.reflect.Field; +import java.lang.reflect.InvocationTargetException; +import java.lang.reflect.Method; + +/** + * BrowserLauncher is a class that provides one static method, openURL, which opens the default + * web browser for the current user of the system to the given URL. It may support other + * protocols depending on the system -- mailto, ftp, etc. -- but that has not been rigorously + * tested and is not guaranteed to work. + *

+ * Yes, this is platform-specific code, and yes, it may rely on classes on certain platforms + * that are not part of the standard JDK. What we're trying to do, though, is to take something + * that's frequently desirable but inherently platform-specific -- opening a default browser -- + * and allow programmers (you, for example) to do so without worrying about dropping into native + * code or doing anything else similarly evil. + *

+ * Anyway, this code is completely in Java and will run on all JDK 1.1-compliant systems without + * modification or a need for additional libraries. All classes that are required on certain + * platforms to allow this to run are dynamically loaded at runtime via reflection and, if not + * found, will not cause this to do anything other than returning an error when opening the + * browser. + *

+ * There are certain system requirements for this class, as it's running through Runtime.exec(), + * which is Java's way of making a native system call. Currently, this requires that a Macintosh + * have a Finder which supports the GURL event, which is true for Mac OS 8.0 and 8.1 systems that + * have the Internet Scripting AppleScript dictionary installed in the Scripting Additions folder + * in the Extensions folder (which is installed by default as far as I know under Mac OS 8.0 and + * 8.1), and for all Mac OS 8.5 and later systems. On Windows, it only runs under Win32 systems + * (Windows 95, 98, and NT 4.0, as well as later versions of all). On other systems, this drops + * back from the inherently platform-sensitive concept of a default browser and simply attempts + * to launch Netscape via a shell command. + *

+ * This code is Copyright 1999-2001 by Eric Albert (ejalbert@cs.stanford.edu) and may be + * redistributed or modified in any form without restrictions as long as the portion of this + * comment from this paragraph through the end of the comment is not removed. The author + * requests that he be notified of any application, applet, or other binary that makes use of + * this code, but that's more out of curiosity than anything and is not required. This software + * includes no warranty. The author is not repsonsible for any loss of data or functionality + * or any adverse or unexpected effects of using this software. + *

+ * Credits: + *
Steven Spencer, JavaWorld magazine (Java Tip 66) + *
Thanks also to Ron B. Yeh, Eric Shapiro, Ben Engber, Paul Teitlebaum, Andrea Cantatore, + * Larry Barowski, Trevor Bedzek, Frank Miedrich, and Ron Rabakukk + * + * @author Eric Albert (ejalbert@cs.stanford.edu) + * @version 1.4b1 (Released June 20, 2001) + */ +public class EjAlbertBrowserLauncher { + + /** + * The Java virtual machine that we are running on. Actually, in most cases we only care + * about the operating system, but some operating systems require us to switch on the VM. */ + private static int jvm; + + /** The browser for the system */ + private static Object browser; + + /** + * Caches whether any classes, methods, and fields that are not part of the JDK and need to + * be dynamically loaded at runtime loaded successfully. + *

+ * Note that if this is false, openURL() will always return an + * IOException. + */ + private static boolean loadedWithoutErrors; + + /** The com.apple.mrj.MRJFileUtils class */ + private static Class mrjFileUtilsClass; + + /** The com.apple.mrj.MRJOSType class */ + private static Class mrjOSTypeClass; + + /** The com.apple.MacOS.AEDesc class */ + private static Class aeDescClass; + + /** The (int) method of com.apple.MacOS.AETarget */ + private static Constructor aeTargetConstructor; + + /** The (int, int, int) method of com.apple.MacOS.AppleEvent */ + private static Constructor appleEventConstructor; + + /** The (String) method of com.apple.MacOS.AEDesc */ + private static Constructor aeDescConstructor; + + /** The findFolder method of com.apple.mrj.MRJFileUtils */ + private static Method findFolder; + + /** The getFileCreator method of com.apple.mrj.MRJFileUtils */ + private static Method getFileCreator; + + /** The getFileType method of com.apple.mrj.MRJFileUtils */ + private static Method getFileType; + + /** The openURL method of com.apple.mrj.MRJFileUtils */ + private static Method openURLm; + + /** The makeOSType method of com.apple.MacOS.OSUtils */ + private static Method makeOSType; + + /** The putParameter method of com.apple.MacOS.AppleEvent */ + private static Method putParameter; + + /** The sendNoReply method of com.apple.MacOS.AppleEvent */ + private static Method sendNoReply; + + /** Actually an MRJOSType pointing to the System Folder on a Macintosh */ + private static Object kSystemFolderType; + + /** The keyDirectObject AppleEvent parameter type */ + private static Integer keyDirectObject; + + /** The kAutoGenerateReturnID AppleEvent code */ + private static Integer kAutoGenerateReturnID; + + /** The kAnyTransactionID AppleEvent code */ + private static Integer kAnyTransactionID; + + /** The linkage object required for JDirect 3 on Mac OS X. */ + private static Object linkage; + + /** The framework to reference on Mac OS X */ + private static final String JDirect_MacOSX = "/System/Library/Frameworks/Carbon.framework/Frameworks/HIToolbox.framework/HIToolbox"; + + /** JVM constant for MRJ 2.0 */ + private static final int MRJ_2_0 = 0; + + /** JVM constant for MRJ 2.1 or later */ + private static final int MRJ_2_1 = 1; + + /** JVM constant for Java on Mac OS X 10.0 (MRJ 3.0) */ + private static final int MRJ_3_0 = 3; + + /** JVM constant for MRJ 3.1 */ + private static final int MRJ_3_1 = 4; + + /** JVM constant for any Windows NT JVM */ + private static final int WINDOWS_NT = 5; + + /** JVM constant for any Windows 9x JVM */ + private static final int WINDOWS_9x = 6; + + /** JVM constant for any other platform */ + private static final int OTHER = -1; + + /** + * The file type of the Finder on a Macintosh. Hardcoding "Finder" would keep non-U.S. English + * systems from working properly. + */ + private static final String FINDER_TYPE = "FNDR"; + + /** + * The creator code of the Finder on a Macintosh, which is needed to send AppleEvents to the + * application. + */ + private static final String FINDER_CREATOR = "MACS"; + + /** The name for the AppleEvent type corresponding to a GetURL event. */ + private static final String GURL_EVENT = "GURL"; + + /** + * The first parameter that needs to be passed into Runtime.exec() to open the default web + * browser on Windows. + */ + private static final String FIRST_WINDOWS_PARAMETER = "/c"; + + /** The second parameter for Runtime.exec() on Windows. */ + private static final String SECOND_WINDOWS_PARAMETER = "start"; + + /** + * The third parameter for Runtime.exec() on Windows. This is a "title" + * parameter that the command line expects. Setting this parameter allows + * URLs containing spaces to work. + */ + private static final String THIRD_WINDOWS_PARAMETER = "\"\""; + + /** + * The shell parameters for Netscape that opens a given URL in an already-open copy of Netscape + * on many command-line systems. + */ + private static final String NETSCAPE_REMOTE_PARAMETER = "-remote"; + private static final String NETSCAPE_OPEN_PARAMETER_START = "'openURL("; + private static final String NETSCAPE_OPEN_PARAMETER_END = ")'"; + + /** + * The message from any exception thrown throughout the initialization process. + */ + private static String errorMessage; + + /** + * An initialization block that determines the operating system and loads the necessary + * runtime data. + */ + static { + loadedWithoutErrors = true; + String osName = System.getProperty("os.name"); + if (osName.startsWith("Mac OS")) { + String mrjVersion = System.getProperty("mrj.version"); + String majorMRJVersion = mrjVersion.substring(0, 3); + try { + double version = Double.valueOf(majorMRJVersion).doubleValue(); + if (version == 2) { + jvm = MRJ_2_0; + } else if (version >= 2.1 && version < 3) { + // Assume that all 2.x versions of MRJ work the same. MRJ 2.1 actually + // works via Runtime.exec() and 2.2 supports that but has an openURL() method + // as well that we currently ignore. + jvm = MRJ_2_1; + } else if (version == 3.0) { + jvm = MRJ_3_0; + } else if (version >= 3.1) { + // Assume that all 3.1 and later versions of MRJ work the same. + jvm = MRJ_3_1; + } else { + loadedWithoutErrors = false; + errorMessage = "Unsupported MRJ version: " + version; + } + } catch (NumberFormatException nfe) { + loadedWithoutErrors = false; + errorMessage = "Invalid MRJ version: " + mrjVersion; + } + } else if (osName.startsWith("Windows")) { + if (osName.indexOf("9") != -1) { + jvm = WINDOWS_9x; + } else { + jvm = WINDOWS_NT; + } + } else { + jvm = OTHER; + } + + if (loadedWithoutErrors) { // if we haven't hit any errors yet + loadedWithoutErrors = loadClasses(); + } + } + + /** + * This class should be never be instantiated; this just ensures so. + */ + private EjAlbertBrowserLauncher() { } + + /** + * Called by a static initializer to load any classes, fields, and methods required at runtime + * to locate the user's web browser. + * @return true if all intialization succeeded + * false if any portion of the initialization failed + */ + private static boolean loadClasses() { + switch (jvm) { + case MRJ_2_0: + try { + Class aeTargetClass = Class.forName("com.apple.MacOS.AETarget"); + Class osUtilsClass = Class.forName("com.apple.MacOS.OSUtils"); + Class appleEventClass = Class.forName("com.apple.MacOS.AppleEvent"); + Class aeClass = Class.forName("com.apple.MacOS.ae"); + aeDescClass = Class.forName("com.apple.MacOS.AEDesc"); + + aeTargetConstructor = aeTargetClass.getDeclaredConstructor(new Class [] { int.class }); + appleEventConstructor = appleEventClass.getDeclaredConstructor(new Class[] { int.class, int.class, aeTargetClass, int.class, int.class }); + aeDescConstructor = aeDescClass.getDeclaredConstructor(new Class[] { String.class }); + + makeOSType = osUtilsClass.getDeclaredMethod("makeOSType", new Class [] { String.class }); + putParameter = appleEventClass.getDeclaredMethod("putParameter", new Class[] { int.class, aeDescClass }); + sendNoReply = appleEventClass.getDeclaredMethod("sendNoReply", new Class[] { }); + + Field keyDirectObjectField = aeClass.getDeclaredField("keyDirectObject"); + keyDirectObject = (Integer) keyDirectObjectField.get(null); + Field autoGenerateReturnIDField = appleEventClass.getDeclaredField("kAutoGenerateReturnID"); + kAutoGenerateReturnID = (Integer) autoGenerateReturnIDField.get(null); + Field anyTransactionIDField = appleEventClass.getDeclaredField("kAnyTransactionID"); + kAnyTransactionID = (Integer) anyTransactionIDField.get(null); + } catch (ClassNotFoundException cnfe) { + errorMessage = cnfe.getMessage(); + return false; + } catch (NoSuchMethodException nsme) { + errorMessage = nsme.getMessage(); + return false; + } catch (NoSuchFieldException nsfe) { + errorMessage = nsfe.getMessage(); + return false; + } catch (IllegalAccessException iae) { + errorMessage = iae.getMessage(); + return false; + } + break; + case MRJ_2_1: + try { + mrjFileUtilsClass = Class.forName("com.apple.mrj.MRJFileUtils"); + mrjOSTypeClass = Class.forName("com.apple.mrj.MRJOSType"); + Field systemFolderField = mrjFileUtilsClass.getDeclaredField("kSystemFolderType"); + kSystemFolderType = systemFolderField.get(null); + findFolder = mrjFileUtilsClass.getDeclaredMethod("findFolder", new Class[] { mrjOSTypeClass }); + getFileCreator = mrjFileUtilsClass.getDeclaredMethod("getFileCreator", new Class[] { File.class }); + getFileType = mrjFileUtilsClass.getDeclaredMethod("getFileType", new Class[] { File.class }); + } catch (ClassNotFoundException cnfe) { + errorMessage = cnfe.getMessage(); + return false; + } catch (NoSuchFieldException nsfe) { + errorMessage = nsfe.getMessage(); + return false; + } catch (NoSuchMethodException nsme) { + errorMessage = nsme.getMessage(); + return false; + } catch (SecurityException se) { + errorMessage = se.getMessage(); + return false; + } catch (IllegalAccessException iae) { + errorMessage = iae.getMessage(); + return false; + } + break; + case MRJ_3_0: + try { + Class linker = Class.forName("com.apple.mrj.jdirect.Linker"); + Constructor constructor = linker.getConstructor(new Class[]{ Class.class }); + linkage = constructor.newInstance(new Object[] { EjAlbertBrowserLauncher.class }); + } catch (ClassNotFoundException cnfe) { + errorMessage = cnfe.getMessage(); + return false; + } catch (NoSuchMethodException nsme) { + errorMessage = nsme.getMessage(); + return false; + } catch (InvocationTargetException ite) { + errorMessage = ite.getMessage(); + return false; + } catch (InstantiationException ie) { + errorMessage = ie.getMessage(); + return false; + } catch (IllegalAccessException iae) { + errorMessage = iae.getMessage(); + return false; + } + break; + case MRJ_3_1: + try { + mrjFileUtilsClass = Class.forName("com.apple.mrj.MRJFileUtils"); + openURLm = mrjFileUtilsClass.getDeclaredMethod("openURL", new Class[] { String.class }); + } catch (ClassNotFoundException cnfe) { + errorMessage = cnfe.getMessage(); + return false; + } catch (NoSuchMethodException nsme) { + errorMessage = nsme.getMessage(); + return false; + } + break; + default: + break; + } + return true; + } + + /** + * Attempts to locate the default web browser on the local system. Caches results so it + * only locates the browser once for each use of this class per JVM instance. + * @return The browser for the system. Note that this may not be what you would consider + * to be a standard web browser; instead, it's the application that gets called to + * open the default web browser. In some cases, this will be a non-String object + * that provides the means of calling the default browser. + */ + private static Object locateBrowser() { + if (browser != null) { + return browser; + } + switch (jvm) { + case MRJ_2_0: + try { + Integer finderCreatorCode = (Integer) makeOSType.invoke(null, new Object[] { FINDER_CREATOR }); + Object aeTarget = aeTargetConstructor.newInstance(new Object[] { finderCreatorCode }); + Integer gurlType = (Integer) makeOSType.invoke(null, new Object[] { GURL_EVENT }); + Object appleEvent = appleEventConstructor.newInstance(new Object[] { gurlType, gurlType, aeTarget, kAutoGenerateReturnID, kAnyTransactionID }); + // Don't set browser = appleEvent because then the next time we call + // locateBrowser(), we'll get the same AppleEvent, to which we'll already have + // added the relevant parameter. Instead, regenerate the AppleEvent every time. + // There's probably a way to do this better; if any has any ideas, please let + // me know. + return appleEvent; + } catch (IllegalAccessException iae) { + browser = null; + errorMessage = iae.getMessage(); + return browser; + } catch (InstantiationException ie) { + browser = null; + errorMessage = ie.getMessage(); + return browser; + } catch (InvocationTargetException ite) { + browser = null; + errorMessage = ite.getMessage(); + return browser; + } + case MRJ_2_1: + File systemFolder; + try { + systemFolder = (File) findFolder.invoke(null, new Object[] { kSystemFolderType }); + } catch (IllegalArgumentException iare) { + browser = null; + errorMessage = iare.getMessage(); + return browser; + } catch (IllegalAccessException iae) { + browser = null; + errorMessage = iae.getMessage(); + return browser; + } catch (InvocationTargetException ite) { + browser = null; + errorMessage = ite.getTargetException().getClass() + ": " + ite.getTargetException().getMessage(); + return browser; + } + String[] systemFolderFiles = systemFolder.list(); + // Avoid a FilenameFilter because that can't be stopped mid-list + for(int i = 0; i < systemFolderFiles.length; i++) { + try { + File file = new File(systemFolder, systemFolderFiles[i]); + if (!file.isFile()) { + continue; + } + // We're looking for a file with a creator code of 'MACS' and + // a type of 'FNDR'. Only requiring the type results in non-Finder + // applications being picked up on certain Mac OS 9 systems, + // especially German ones, and sending a GURL event to those + // applications results in a logout under Multiple Users. + Object fileType = getFileType.invoke(null, new Object[] { file }); + if (FINDER_TYPE.equals(fileType.toString())) { + Object fileCreator = getFileCreator.invoke(null, new Object[] { file }); + if (FINDER_CREATOR.equals(fileCreator.toString())) { + browser = file.toString(); // Actually the Finder, but that's OK + return browser; + } + } + } catch (IllegalArgumentException iare) { + browser = browser; + errorMessage = iare.getMessage(); + return null; + } catch (IllegalAccessException iae) { + browser = null; + errorMessage = iae.getMessage(); + return browser; + } catch (InvocationTargetException ite) { + browser = null; + errorMessage = ite.getTargetException().getClass() + ": " + ite.getTargetException().getMessage(); + return browser; + } + } + browser = null; + break; + case MRJ_3_0: + case MRJ_3_1: + browser = ""; // Return something non-null + break; + case WINDOWS_NT: + browser = "cmd.exe"; + break; + case WINDOWS_9x: + browser = "command.com"; + break; + case OTHER: + default: + browser = "netscape"; + break; + } + return browser; + } + + /** + * Attempts to open the default web browser to the given URL. + * @param url The URL to open + * @throws IOException If the web browser could not be located or does not run + */ + public static void openURL(String url) throws IOException { + if (!loadedWithoutErrors) { + throw new IOException("Exception in finding browser: " + errorMessage); + } + Object browser = locateBrowser(); + if (browser == null) { + throw new IOException("Unable to locate browser: " + errorMessage); + } + + switch (jvm) { + case MRJ_2_0: + Object aeDesc = null; + try { + aeDesc = aeDescConstructor.newInstance(new Object[] { url }); + putParameter.invoke(browser, new Object[] { keyDirectObject, aeDesc }); + sendNoReply.invoke(browser, new Object[] { }); + } catch (InvocationTargetException ite) { + throw new IOException("InvocationTargetException while creating AEDesc: " + ite.getMessage()); + } catch (IllegalAccessException iae) { + throw new IOException("IllegalAccessException while building AppleEvent: " + iae.getMessage()); + } catch (InstantiationException ie) { + throw new IOException("InstantiationException while creating AEDesc: " + ie.getMessage()); + } finally { + aeDesc = null; // Encourage it to get disposed if it was created + browser = null; // Ditto + } + break; + case MRJ_2_1: + Runtime.getRuntime().exec(new String[] { (String) browser, url } ); + break; + case MRJ_3_0: + int[] instance = new int[1]; + int result = ICStart(instance, 0); + if (result == 0) { + int[] selectionStart = new int[] { 0 }; + byte[] urlBytes = url.getBytes(); + int[] selectionEnd = new int[] { urlBytes.length }; + result = ICLaunchURL(instance[0], new byte[] { 0 }, urlBytes, + urlBytes.length, selectionStart, + selectionEnd); + if (result == 0) { + // Ignore the return value; the URL was launched successfully + // regardless of what happens here. + ICStop(instance); + } else { + throw new IOException("Unable to launch URL: " + result); + } + } else { + throw new IOException("Unable to create an Internet Config instance: " + result); + } + break; + case MRJ_3_1: + try { + openURLm.invoke(null, new Object[] { url }); + } catch (InvocationTargetException ite) { + throw new IOException("InvocationTargetException while calling openURL: " + ite.getMessage()); + } catch (IllegalAccessException iae) { + throw new IOException("IllegalAccessException while calling openURL: " + iae.getMessage()); + } + break; + case WINDOWS_NT: + case WINDOWS_9x: + // Add quotes around the URL to allow ampersands and other special + // characters to work. + Process process = Runtime.getRuntime().exec(new String[] { (String) browser, + FIRST_WINDOWS_PARAMETER, + SECOND_WINDOWS_PARAMETER, + THIRD_WINDOWS_PARAMETER, + '"' + url + '"' }); + // This avoids a memory leak on some versions of Java on Windows. + // That's hinted at in . + try { + process.waitFor(); + process.exitValue(); + } catch (InterruptedException ie) { + throw new IOException("InterruptedException while launching browser: " + ie.getMessage()); + } + break; + case OTHER: + // Assume that we're on Unix and that Netscape is installed + + // First, attempt to open the URL in a currently running session of Netscape + process = Runtime.getRuntime().exec(new String[] { (String) browser, + NETSCAPE_REMOTE_PARAMETER, + NETSCAPE_OPEN_PARAMETER_START + + url + + NETSCAPE_OPEN_PARAMETER_END }); + try { + int exitCode = process.waitFor(); + if (exitCode != 0) { // if Netscape was not open + Runtime.getRuntime().exec(new String[] { (String) browser, url }); + } + } catch (InterruptedException ie) { + throw new IOException("InterruptedException while launching browser: " + ie.getMessage()); + } + break; + default: + // This should never occur, but if it does, we'll try the simplest thing possible + Runtime.getRuntime().exec(new String[] { (String) browser, url }); + break; + } + } + + /** + * Methods required for Mac OS X. The presence of native methods does not cause + * any problems on other platforms. + */ + /* + private native static int ICStart(int[] instance, int signature); + private native static int ICStop(int[] instance); + private native static int ICLaunchURL(int instance, byte[] hint, byte[] data, int len, + int[] selectionStart, int[] selectionEnd); + */ + private static int ICStart(int[] instance, int signature) { return 0; } + private static int ICStop(int[] instance) { return 0; } + private static int ICLaunchURL(int instance, byte[] hint, byte[] data, int len, + int[] selectionStart, int[] selectionEnd) { return 0; } +} diff --git a/src/org/ibex/util/FileNameEncoder.java b/src/org/ibex/util/FileNameEncoder.java new file mode 100644 index 0000000..e68bba2 --- /dev/null +++ b/src/org/ibex/util/FileNameEncoder.java @@ -0,0 +1,50 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; +import java.util.*; +import java.io.*; + +/** provides commands to urlencode and urldecode strings, making sure + * to escape sequences which have special meanings in filenames */ +public class FileNameEncoder { + + private static final char[] hex = + new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' }; + + public static String encode(String s) { + StringBuffer sb = new StringBuffer(); + try { + byte[] b = s.getBytes("UTF-8"); + for(int i=0; i 126 || c == '%' || (i == 0 && c == '.')) + sb.append("%" + hex[(b[i] & 0xf0) >> 8] + hex[b[i] & 0xf]); + else sb.append(c); + } + return sb.toString(); + } catch (UnsupportedEncodingException uee) { + throw new Error("this should never happen; Java spec mandates UTF-8 support"); + } + } + + public static String decode(String s) { + StringBuffer sb = new StringBuffer(); + byte[] b = new byte[s.length() * 2]; + int bytes = 0; + for(int i=0; i= min && s.charAt(start) <= max)) return -1; + return start + 1; + } + } + + public static class Reference extends Grammar { + String key; + public Reference(String key) { this.key = key; } + public int match(String s, int start, Hash v, JSScope scope) throws JSExn { + return ((Grammar)scope.get(key)).matchAndWrite(s, start, v, scope, key); + } + } +} diff --git a/src/org/ibex/util/Hash.java b/src/org/ibex/util/Hash.java new file mode 100644 index 0000000..4b38870 --- /dev/null +++ b/src/org/ibex/util/Hash.java @@ -0,0 +1,174 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +import java.util.*; + +/** Implementation of an unsynchronized hash table, with one or two + * keys, using Radke's quadradic residue linear probing instead of + * buckets to minimize object count (less allocations, faster GC). + * See C. Radke, Communications of the ACM, 1970, 103-105 + * + * Not threadsafe. + */ +public class Hash { + /** this object is inserted as key in a slot when the + * corresponding value is removed -- this ensures that the + * probing sequence for any given key remains the same even if + * other keys are removed. + */ + private static Object placeholder = new Object(); + + /** the number of entries with at least one non-null key */ + private int usedslots = 0; + + /** the number of entries with non-null values */ + protected int size = 0; + + /** when num_slots < loadFactor * size, rehash into a bigger table */ + private final int loadFactor; + + /** primary keys */ + private Object[] keys1 = null; + + /** secondary keys; null if no secondary key has ever been added */ + private Object[] keys2 = null; + + /** the values for the table */ + private Object[] vals = null; + + /** the number of entries with a non-null value */ + public int size() { return size; } + + /** empties the table */ + public void clear() { + size = 0; + usedslots = 0; + for(int i=0; i vals.length) rehash(); + int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode()); + int dest = Math.abs(hash) % vals.length; + int odest = dest; + boolean plus = true; + int tries = 1; + while (true) { + Object hk1 = keys1[dest]; + Object hk2 = keys2 == null ? null : keys2[dest]; + if (hk1 == null && hk2 == null) { // empty slot + if (v == null) return; + size++; + usedslots++; + break; + } + + if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) && // replacing former entry + (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) { + + // we don't actually remove things from the table; rather, we insert a placeholder + if (v == null) { + k1 = placeholder; + k2 = null; + size--; + } + break; + } + + dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length); + if (plus) tries++; + plus = !plus; + } + + keys1[dest] = k1; + if (k2 != null && keys2 == null) keys2 = new Object[keys1.length]; + if (keys2 != null) keys2[dest] = k2; + vals[dest] = v; + } + + private class HashEnum implements java.util.Enumeration { + private int iterator = 0; + private int found = 0; + + public boolean hasMoreElements() { + return found < usedslots; + } + + public Object nextElement() { + if (!hasMoreElements()) throw new java.util.NoSuchElementException(); + + Object o = null; + while (o == null) o = keys1[iterator++]; + if (o == null) throw new IllegalStateException("Didn't find an element, when I should have."); + found++; + + return o; + } + } +} + + diff --git a/src/org/ibex/util/InputStreamToByteArray.java b/src/org/ibex/util/InputStreamToByteArray.java new file mode 100644 index 0000000..7e19644 --- /dev/null +++ b/src/org/ibex/util/InputStreamToByteArray.java @@ -0,0 +1,35 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; +import java.io.*; + +public class InputStreamToByteArray { + + /** scratch space for isToByteArray() */ + private static byte[] workspace = new byte[16 * 1024]; + + /** Trivial method to completely read an InputStream */ + public static synchronized byte[] convert(InputStream is) throws IOException { + int pos = 0; + while (true) { + int numread = is.read(workspace, pos, workspace.length - pos); + if (numread == -1) break; + else if (pos + numread < workspace.length) pos += numread; + else { + pos += numread; + byte[] temp = new byte[workspace.length * 2]; + System.arraycopy(workspace, 0, temp, 0, workspace.length); + workspace = temp; + } + } + byte[] ret = new byte[pos]; + System.arraycopy(workspace, 0, ret, 0, pos); + return ret; + } + +} diff --git a/src/org/ibex/util/KnownLength.java b/src/org/ibex/util/KnownLength.java new file mode 100644 index 0000000..06118bb --- /dev/null +++ b/src/org/ibex/util/KnownLength.java @@ -0,0 +1,25 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; +import java.io.*; + +/** a generic interface for things that "know" their length */ +public interface KnownLength { + + public abstract int getLength(); + + public static class KnownLengthInputStream extends FilterInputStream implements KnownLength { + int length; + public int getLength() { return length; } + public KnownLengthInputStream(java.io.InputStream parent, int length) { + super(parent); + this.length = length; + } + } + +} diff --git a/src/org/ibex/util/LineReader.java b/src/org/ibex/util/LineReader.java new file mode 100644 index 0000000..429c218 --- /dev/null +++ b/src/org/ibex/util/LineReader.java @@ -0,0 +1,46 @@ +package org.ibex.util; +import java.io.*; + +public class LineReader { + + private int MAXBUF = 1024 * 16; + char[] buf = new char[MAXBUF]; + int buflen = 0; + Reader r; + Vec pushback = new Vec(); + + public LineReader(Reader r) { this.r = r; } + + public void pushback(String s) { pushback.push(s); } + + public String readLine() throws IOException { + while(true) { + if (pushback.size() > 0) return (String)pushback.pop(); + for(int i=0; i all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; +import org.ibex.js.*; +import java.io.*; +import java.util.*; +import java.net.*; + +/** easy to use logger */ +public class Log { + + public static boolean on = System.getProperty("ibex.log.on", "true").equals("true"); + public static boolean color = System.getProperty("ibex.log.color", "true").equals("true"); + public static boolean verbose = System.getProperty("ibex.log.verbose", "false").equals("true"); + public static boolean logDates = System.getProperty("ibex.log.dates", "false").equals("true"); + public static boolean notes = System.getProperty("ibex.log.notes.on", "true").equals("true"); + public static int maximumNoteLength = Integer.parseInt(System.getProperty("ibex.log.notes.maximumLength", (1024 * 32)+"")); + public static boolean rpc = false; + public static Date lastDate = null; + + public static PrintStream logstream = System.err; + + public static void flush() { logstream.flush(); } + public static void email(String address) { throw new Error("FIXME not supported"); } + public static void file(String filename) throws IOException { + // FIXME security + logstream = new PrintStream(new FileOutputStream(filename)); + } + public static void tcp(String host, int port) throws IOException { + // FIXME security + logstream = new PrintStream(new Socket(InetAddress.getByName(host), port).getOutputStream()); + } + + private static Hashtable threadAnnotations = new Hashtable(); + public static void setThreadAnnotation(String s) { threadAnnotations.put(Thread.currentThread(), s); } + + /** + * Notes can be used to attach log messages to the current thread + * if you're not sure you want them in the log just yet. + * Originally designed for retroactively logging socket-level + * conversations only if an error is encountered + */ + public static void note(String s) { + if (!notes) return; + StringBuffer notebuf = notebuf(); + notebuf.append(s); + if (notebuf.length() > maximumNoteLength) { + notebuf.reverse(); + notebuf.setLength(maximumNoteLength * 3 / 4); + notebuf.reverse(); + } + } + public static void clearnotes() { if (!notes) return; notebuf().setLength(0); } + private static Hashtable notebufs = new Hashtable(); + private static StringBuffer notebuf() { + StringBuffer ret = (StringBuffer)notebufs.get(Thread.currentThread()); + if (ret == null) { + ret = new StringBuffer(16 * 1024); + notebufs.put(Thread.currentThread(), ret); + } + return ret; + } + + /** true iff nothing has yet been logged */ + public static boolean firstMessage = true; + + /** message can be a String or a Throwable */ + public static synchronized void echo(Object o, Object message) { log(o, message, ECHO); } + public static synchronized void diag(Object o, Object message) { log(o, message, DIAGNOSTIC); } + public static synchronized void debug(Object o, Object message) { log(o, message, DEBUG); } + public static synchronized void info(Object o, Object message) { log(o, message, INFO); } + public static synchronized void warn(Object o, Object message) { log(o, message, WARN); } + public static synchronized void error(Object o, Object message) { log(o, message, ERROR); } + + // these two logging levels serve ONLY to change the color; semantically they are the same as DEBUG + private static final int DIAGNOSTIC = -2; + private static final int ECHO = -1; + + // the usual log4j levels, minus FAIL (we just throw an Error in that case) + public static final int DEBUG = 0; + public static final int INFO = 1; + public static final int WARN = 2; + public static final int ERROR = 3; + public static final int SILENT = Integer.MAX_VALUE; + public static int level = INFO; + + private static final int BLUE = 34; + private static final int GREEN = 32; + private static final int CYAN = 36; + private static final int RED = 31; + private static final int PURPLE = 35; + private static final int BROWN = 33; + private static final int GRAY = 37; + + private static String colorize(int color, boolean bright, String s) { + if (!Log.color) return s; + return + "\033[40;" + (bright?"1;":"") + color + "m" + + s + + "\033[0m"; + } + + private static String lastClassName = null; + private static synchronized void log(Object o, Object message, int level) { + if (level < Log.level) return; + if (firstMessage && !logDates) { + firstMessage = false; + logstream.println(colorize(GREEN, false, "===========================================================================")); + + // FIXME later: causes problems with method pruning + //diag(Log.class, "Logging enabled at " + new java.util.Date()); + + if (color) diag(Log.class, "logging messages in " + + colorize(BLUE, true, "c") + + colorize(RED, true, "o") + + colorize(CYAN, true, "l") + + colorize(GREEN, true, "o") + + colorize(PURPLE, true, "r")); + } + + String classname; + if (o instanceof Class) { + classname = ((Class)o).getName(); + if (classname.indexOf('.') != -1) classname = classname.substring(classname.lastIndexOf('.') + 1); + } + else if (o instanceof String) classname = (String)o; + else classname = o.getClass().getName(); + + if (classname.equals(lastClassName)) classname = ""; + else lastClassName = classname; + + if (classname.length() > (logDates ? 14 : 20)) classname = classname.substring(0, (logDates ? 14 : 20)); + while (classname.length() < (logDates ? 14 : 20)) classname = " " + classname; + classname = classname + (classname.trim().length() == 0 ? " " : ": "); + classname = colorize(GRAY, true, classname); + classname = classname.replace('$', '.'); + + if (logDates) { + Date d = new Date(); + if (lastDate == null || d.getYear() != lastDate.getYear() || d.getMonth() != lastDate.getMonth() || d.getDay() != lastDate.getDay()) { + String now = new java.text.SimpleDateFormat("EEE dd MMM yyyy").format(d); + logstream.println(); + logstream.println(colorize(GRAY, false, "=== " + now + " ==========================================================")); + } + java.text.DateFormat df = new java.text.SimpleDateFormat("[EEE HH:mm:ss] "); + classname = df.format(d) + classname; + lastDate = d; + } + + String annot = (String)threadAnnotations.get(Thread.currentThread()); + if (annot != null) classname += annot; + + if (message instanceof Throwable) { + if (level < ERROR) level = WARN; + ByteArrayOutputStream baos = new ByteArrayOutputStream(); + ((Throwable)message).printStackTrace(new PrintStream(baos)); + if (notes && notebuf().length() > 0) { + PrintWriter pw = new PrintWriter(baos); + pw.println(); + pw.println("Thread notes:"); + pw.println(notebuf().toString()); + clearnotes(); + pw.flush(); + } + byte[] b = baos.toByteArray(); + BufferedReader br = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(b))); + String s = null; + try { + String m = ""; + while((s = br.readLine()) != null) m += s + "\n"; + if (m.length() > 0) log(o, m.substring(0, m.length() - 1), level); + } catch (IOException e) { + // FEATURE: use org.ibex.io.Stream's here + logstream.println(colorize(RED, true, "Logger: exception thrown by ByteArrayInputStream; this should not happen")); + } + lastClassName = ""; + return; + } + + String str = message.toString(); + if (str.indexOf('\n') != -1) lastClassName = ""; + while(str.indexOf('\t') != -1) + str = str.substring(0, str.indexOf('\t')) + " " + str.substring(str.indexOf('\t') + 1); + + classname = colorize(GRAY, false, classname); + int levelcolor = GRAY; + boolean bright = true; + switch (level) { + case DIAGNOSTIC: levelcolor = GREEN; bright = false; break; + case ECHO: levelcolor = BLUE; bright = true; break; + case DEBUG: levelcolor = BROWN; bright = true; break; + case INFO: levelcolor = GRAY; bright = false; break; + case WARN: levelcolor = BROWN; bright = false; break; + case ERROR: levelcolor = RED; bright = true; break; + } + + while(str.indexOf('\n') != -1) { + logstream.println(classname + colorize(levelcolor, bright, str.substring(0, str.indexOf('\n')))); + classname = logDates ? " " : " "; + classname = colorize(GRAY,false,classname); + str = str.substring(str.indexOf('\n') + 1); + } + logstream.println(classname + colorize(levelcolor, bright, str)); + } + + public static void recursiveLog(String indent, String name, Object o) throws JSExn { + if (!name.equals("")) name += " : "; + + if (o == null) { + JS.log(indent + name + ""); + + } else if (o instanceof JSArray) { + JS.log(indent + name + ""); + JSArray na = (JSArray)o; + for(int i=0; i"); + JS s = (JS)o; + Enumeration e = s.keys(); + while(e.hasMoreElements()) { + Object key = e.nextElement(); + if (key != null) + recursiveLog(indent + " ", key.toString(), + (key instanceof Integer) ? + s.get(((Integer)key)) : s.get(key.toString())); + } + } else { + JS.log(indent + name + o); + + } + } + +} diff --git a/src/org/ibex/util/MSPack.c b/src/org/ibex/util/MSPack.c new file mode 100644 index 0000000..f09cf35 --- /dev/null +++ b/src/org/ibex/util/MSPack.c @@ -0,0 +1,202 @@ +/* +UserInfo: + On start: + 0: Addr of CAB/EXE + 1: Length of CAB/EXE + On Edit: + 2: Addr of output_table array + +Exit codes: + 0: Success + 1: Internal Error + 2: Invalid CAB +*/ + +#include +#include +#include +#include +#include + +#include "mspack.h" + +#define MAX(a,b) (((a)>(b))?(a):(b)) +#define MIN(a,b) (((a)<(b))?(a):(b)) +#define MAX_MEMBERS 64 + +char *xstrdup(const char *s) { + char *ret = strdup(s); + if(ret == NULL) exit(1); + return ret; +} + +typedef struct { + char *addr; + int pos; + int size; + int length; + int writable; +} mem_buf_t; + +static mem_buf_t *cab_mem_buf = NULL; + +static void mem_buf_grow(mem_buf_t *buf,size_t newsize) { + size_t new_len; + char *p; + if(buf->length < 0) exit(1); + if(newsize <= buf->length) return; + new_len = MAX(buf->length ? buf->length*2 : 65536,newsize); + p = realloc(buf->addr,new_len); + if(p == NULL) exit(1); + buf->addr = p; + buf->length = new_len; +} + +static struct { + char *filename; + mem_buf_t buf; +} write_buf_table[MAX_MEMBERS]; + +static struct { + char *filename; + char *data; + int length; +} output_table[MAX_MEMBERS+1]; + +static struct mspack_file *my_open(struct mspack_system *sys, char *filename, int mode) { + mem_buf_t *buf = NULL; + int i; + if(strcmp(filename,"/dev/cab")==0) { + if(mode != MSPACK_SYS_OPEN_READ) return NULL; + buf = cab_mem_buf; + } else { + if(mode != MSPACK_SYS_OPEN_WRITE) return NULL; + + for(i=0;iwritable = 1; + break; + } + } + } + + return (struct mspack_file *) buf; +} + +static void my_close(struct mspack_file *buf_) { + mem_buf_t *buf = (mem_buf_t*) buf_; + /* NO OP */ +} + +static int my_read(struct mspack_file *buf_, void *out, int count) { + mem_buf_t *buf = (mem_buf_t*) buf_; + count = MIN(buf->size - buf->pos, count); + memcpy(out,buf->addr + buf->pos,count); + buf->pos += count; + return count; +} + +static int my_write(struct mspack_file *buf_, void *in, int count) { + mem_buf_t *buf = (mem_buf_t*) buf_; + if(!buf->writable) return -1; + if(buf->length < buf->pos + count) mem_buf_grow(buf,buf->pos + count); + memcpy(buf->addr+buf->pos,in,count); + buf->pos += count; + buf->size = MAX(buf->size,buf->pos); + return count; +} + +static int my_seek(struct mspack_file *buf_, off_t off, int mode) { + mem_buf_t *buf = (mem_buf_t*) buf_; + int newpos; + switch(mode) { + case MSPACK_SYS_SEEK_START: newpos = off; break; + case MSPACK_SYS_SEEK_CUR: newpos = buf->pos + off; break; + case MSPACK_SYS_SEEK_END: newpos = buf->size - off; break; + default: return -1; + } + if(newpos < 0) return -1; + if(newpos > buf->size) { + if(!buf->writable) return -1; + if(newpos > buf->length) + mem_buf_grow(buf,newpos); + } + buf->pos = newpos; + return 0; +} + +static off_t my_tell(struct mspack_file *buf_) { + mem_buf_t *buf = (mem_buf_t*) buf_; + return buf ? buf->pos : 0; +} + +// FEATURE: Remove this to possibly avoid pulling in stdio from libc +// (it may be getting pulled in anyway from malloc or something) +static void my_message(struct mspack_file *file, char *format, ...) { + va_list ap; + va_start(ap, format); + vfprintf(stderr, format, ap); + va_end(ap); + fputc((int) '\n', stderr); + fflush(stderr); +} + +static void *my_alloc(struct mspack_system *sys, size_t size) { return malloc(size); } +static void my_free(void *p) { free(p); } +static void my_copy(void *src, void *dest, size_t bytes) { memcpy(dest, src, bytes); } + +static struct mspack_system my_system = { + &my_open, + &my_close, + &my_read, + &my_write, + &my_seek, + &my_tell, + &my_message, + &my_alloc, + &my_free, + &my_copy, + NULL +}; + +extern char *user_info[1024]; + +int mspack_main() { + struct mscab_decompressor *decomp; + struct mscabd_cabinet *cab; + struct mscabd_file *file; + mem_buf_t mem_buf; + size_t size = (size_t)user_info[1]; + int i; + + mem_buf.addr = user_info[0]; + mem_buf.pos = mem_buf.writable = 0; + mem_buf.length = -1; + mem_buf.size = size; + + cab_mem_buf = &mem_buf; + + decomp = mspack_create_cab_decompressor(&my_system); + if(!decomp) exit(1); + + cab = decomp->search(decomp,"/dev/cab"); + if(!cab) exit(2); + + for(file = cab->files;file;file=file->next) + decomp->extract(decomp,file,file->filename); + + decomp->close(decomp,cab); + mspack_destroy_cab_decompressor(decomp); + + for(i=0;i")) + isconstructed = true; + + // we can only prune static fields (to avoid altering object layout, which is hardcoded into + // CNI code), but that's okay since instance fields don't contribute to binary size + Field[] fields = clazz.getFields(); + for(int i=0; i", Type.VOID, Type.NO_ARGS, Constants.INVOKESPECIAL)); + il.append(InstructionConstants.ATHROW); + mg.setMaxStack(); + mg.setMaxLocals(); + mg.removeExceptions(); + mg.removeLocalVariables(); + mg.removeExceptionHandlers(); + mg.removeLineNumbers(); + cg.replaceMethod(methods[i], mg.getMethod()); + il.dispose(); + } + } + } + + // FIXME: chain up to superclass' ... that might remove the need for this hack + // FIXME: gcj compiling in jar-at-a-time mode can't be convinced to let classes outside the jar override + // the ones inside the jar + good = true; + + if (!good && !clazz.isAbstract() && !clazz.isInterface()) { + System.out.println("DROPPING " + clazz.getClassName()); + JavaClass[] ifaces = clazz.getInterfaces(); + String[] ifacestrings = new String[ifaces.length]; + for(int i=0; i 0 && (sig.charAt(0) == 'L' || sig.charAt(0) == '[')) { + if (sig.charAt(0) == 'L') sig = sig.substring(1, sig.length() - 1); + else if (sig.charAt(0) == '[') sig = sig.substring(1, sig.length()); + } + if (sig.length() <= 1) return null; + if (sig.equals("")) return null; + if (sig.startsWith(" 0 && (sig.charAt(0) == 'L' || sig.charAt(0) == '[')) { + if (sig.charAt(0) == 'L') sig = sig.substring(1, sig.length() - 1); + else if (sig.charAt(0) == '[') sig = sig.substring(1, sig.length()); + } + if (sig.length() <= 1) return; + if (sig.equals("")) return; + if (sig.startsWith("") && jc.getClassName().startsWith("java.lang.reflect.")) return; + + if (dest.contains(method)) return; + dest.add(method); + + if (method.getName().equals("") && jc.getSuperClass() != null) + loadMethod(jc.getSuperClass().getClassName() + "."); + + if (method.isStatic() || method.getName().equals("")) loadMethod(jc.getClassName() + "."); + if (method.getName().equals("")) { + // FIXME: generalize to all perinstancemethods + constructed.add(jc); + HashSet hs = (HashSet)uponconstruction.get(jc); + if (hs != null) { + Iterator it = hs.iterator(); + while(it.hasNext()) visitJavaMethod(jc, (Method)it.next()); + } + loadMethod(jc.getClassName() + ".equals"); + loadMethod(jc.getClassName() + ".hashCode"); + loadMethod(jc.getClassName() + ".toString"); + loadMethod(jc.getClassName() + ".finalize"); + loadMethod(jc.getClassName() + ".clone"); + } + + ConstantPoolGen cpg = new ConstantPoolGen(method.getConstantPool()); + if (!method.isStatic() && !constructed.contains(jc)) { + HashSet hs = (HashSet)uponconstruction.get(jc); + if (hs == null) uponconstruction.put(jc, hs = new HashSet()); + hs.add(method); + markMethodInSubclasses(jc, method, cpg); + dest.remove(method); + return; + } + + level += 2; + for(int i=0; i"); + } + if (instr instanceof CPInstruction) load(((CPInstruction)instr).getType(cpg)); + if (instr instanceof TypedInstruction) load(((TypedInstruction)instr).getType(cpg)); + if (instr instanceof NEW) loadMethod(((NEW)instr).getLoadClassType(cpg).getClassName() + "."); + if (instr instanceof org.apache.bcel.generic.FieldOrMethod) + load(((org.apache.bcel.generic.FieldOrMethod)instr).getClassType(cpg)); + if (instr instanceof org.apache.bcel.generic.FieldInstruction) { + load(((org.apache.bcel.generic.FieldInstruction)instr).getFieldType(cpg)); + load(((org.apache.bcel.generic.FieldInstruction)instr).getType(cpg)); + String fieldName = ((org.apache.bcel.generic.FieldInstruction)instr).getFieldName(cpg); + JavaClass jc2 = repo.loadClass(((ObjectType)((org.apache.bcel.generic.FieldInstruction)instr). + getLoadClassType(cpg)).getClassName()); + Field[] fields = jc2.getFields(); + for(int j=0; j"); + } + + public void visitJavaClass(JavaClass clazz) throws Exception { + if (dest.contains(clazz)) return; + dest.add(clazz); + + ConstantPoolGen cpg = new ConstantPoolGen(clazz.getConstantPool()); + level += 2; + for(int i=0; i")) return; + if (m.getName().equals("equals")) return; + if (m.getName().equals("hashCode")) return; + if (m.getName().equals("clone")) return; + if (m.getName().equals("finalize")) return; + if (m.getName().equals("toString")) return; + String sig = getMethodSignature(m, cpg); + Method[] submethods = getMethods(subclass); + for(int j=0; j")) return; + HashSet s = (HashSet)subclasses.get(c); + if (s == null) return; + Object[] subclasses = s.toArray(); + for(int i=0; i all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +/** packs 8-bit bytes into a String of 7-bit chars (to avoid the UTF-8 non-ASCII penalty) */ +public class PackBytesIntoString { + + public static String pack(byte[] b, int off, int len) throws IllegalArgumentException { + if (len % 7 != 0) throw new IllegalArgumentException("len must be a multiple of 7"); + StringBuffer ret = new StringBuffer(); + for(int i=off; i=0; j--) { + l <<= 8; + l |= (b[i + j] & 0xff); + } + for(int j=0; j<8; j++) { + ret.append((char)(l & 0x7f)); + l >>= 7; + } + } + return ret.toString(); + } + + public static byte[] unpack(String s) throws IllegalArgumentException { + if (s.length() % 8 != 0) throw new IllegalArgumentException("string length must be a multiple of 8"); + byte[] ret = new byte[(s.length() / 8) * 7]; + for(int i=0; i=0; j--) { + l <<= 7; + l |= (s.charAt(i + j) & 0x7fL); + } + for(int j=0; j<7; j++) { + ret[(i / 8) * 7 + j] = (byte)(l & 0xff); + l >>= 8; + } + } + return ret; + } +} + diff --git a/src/org/ibex/util/Preprocessor.java b/src/org/ibex/util/Preprocessor.java new file mode 100644 index 0000000..a226731 --- /dev/null +++ b/src/org/ibex/util/Preprocessor.java @@ -0,0 +1,342 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +import gnu.regexp.*; +import java.util.*; +import java.io.*; + +/** + * A VERY crude, inefficient Java preprocessor + * + * //#define FOO bar baz -- replace all instances of token FOO with "bar baz" + * //#replace foo/bar baz/bop -- DUPLICATE everything between here and //#end, + * replacing foo with bar and baz with bop in the *second* copy + * //#switch(EXPR) -- switch on strings + * case "case1": + * //#end + * + * Replacements are done on a token basis. Tokens are defined as a + * sequence of characters which all belong to a single class. The + * two character classes are: + * + * - [a-zA-Z0-9_] + * - all other non-whitespace characters + */ +public class Preprocessor { + + public static String replaceAll(String source, String regexp, String replaceWith) { + try { + RE re = new RE(regexp, 0, RESyntax.RE_SYNTAX_PERL5); + return (String)re.substituteAll(source, replaceWith); + } catch (Exception e) { + e.printStackTrace(); + return null; + } + } + + public static void main(String[] args) throws Exception { + BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); + BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); + + // process stdin to stdout + Preprocessor cc = new Preprocessor(br, bw); + Vector err = cc.process(); + bw.flush(); + + // handle errors + boolean errors = false; + for (int i=0; i < err.size(); i++) { if (err.get(i) instanceof Error) errors = true; System.err.println(err.get(i)); } + if (errors) throw new Exception(); + } + + private Reader r; + private Writer w; + private LineNumberReader in; + private PrintWriter out; + + private Hashtable replace = new Hashtable(); + private Hashtable repeatreplace = null; + private Vector sinceLastRepeat = null; + private Vector err = new Vector(); + + private int enumSwitch = 0; // number appended to variable used in switch implementation + + + public Preprocessor(Reader reader, Writer writer) { + setReader(reader); + setWriter(writer); + } + + public void setReader(Reader reader) { r = reader; if (r != null) in = new LineNumberReader(r); } + public Reader getReader() { return r; } + + public void setWriter(Writer writer) { w = writer; if (w != null) out = new PrintWriter(w); } + public Writer getWriter() { return w; } + + + /** process data from reader, write to writer, return vector of errors */ + public Vector process() throws IOException { + err.clear(); + + String s = null; +PROCESS: + while((s = in.readLine()) != null) { + if (sinceLastRepeat != null) sinceLastRepeat.addElement(s); + String trimmed = s.trim(); + + if (trimmed.startsWith("//#define ")) { + if (trimmed.length() == 9 || trimmed.charAt(9) != ' ') { + err.add(new Error("#define badly formed, ignored")); continue PROCESS; + } + int keyStart = indexOfNotWS(trimmed, 9); + if (keyStart == -1) { + err.add(new Error("#define requires KEY")); continue PROCESS; + } + int keyEnd = indexOfWS(trimmed, keyStart); + + int macroStart = trimmed.indexOf('('); + int macroEnd = trimmed.indexOf(')'); + if (macroStart > keyEnd) { + // no macro is defined, just make sure something dumb like KEYNA)ME hasn't been done + if (macroEnd < keyEnd) { err.add(new Error("#define key contains invalid char: ')'")); continue PROCESS; } + macroStart = macroEnd = -1; + } + + if (macroStart == 0) { + err.add(new Error("#define macro requires name")); continue PROCESS; + } else if (macroStart > 0) { + if (macroStart > macroEnd) { err.add(new Error("#define macro badly formed")); continue PROCESS; } + if (macroStart+1 == macroEnd) { err.add(new Error("#define macro requires property name")); continue PROCESS; } + + JSFunctionMacro fm = new JSFunctionMacro(); + String key = trimmed.substring(keyStart, macroStart); + String unbound = trimmed.substring(macroStart +1, macroEnd); + int unboundDiv = unbound.indexOf(','); + if (unboundDiv == -1) { + fm.unbound1 = unbound; + } else { + fm.unbound1 = unbound.substring(0, unboundDiv); + fm.unbound2 = unbound.substring(unboundDiv +1); + if (fm.unbound1.length() == 0) { err.add(new Error("#define macro property 1 requires name")); continue PROCESS; } + if (fm.unbound2.length() == 0) { err.add(new Error("#define macro property 1 requires name")); continue PROCESS; } + } + fm.expression = trimmed.substring(keyEnd).trim(); + replace.put(key, fm); + } else { + String key = trimmed.substring(keyStart, keyEnd); + String val = trimmed.substring(keyEnd).trim(); + replace.put(key, val); + } + out.print("\n"); // preserve line numbers + + } else if (trimmed.startsWith("//#repeat ")) { + trimmed = trimmed.substring(9); + while(trimmed.charAt(trimmed.length() - 1) == '\\') { + String s2 = in.readLine().trim(); + if (s2.startsWith("//")) s2 = s2.substring(2).trim(); + trimmed = trimmed.substring(0, trimmed.length() - 1) + " " + s2; + out.print("\n"); // preserve line numbers + } + StringTokenizer st = new StringTokenizer(trimmed, " "); + repeatreplace = (Hashtable)replace.clone(); + while (st.hasMoreTokens()) { + String tok = st.nextToken().trim(); + String key = tok.substring(0, tok.indexOf('/')); + String val = tok.substring(tok.indexOf('/') + 1); + repeatreplace.put(key, val); + } + sinceLastRepeat = new Vector(); + out.print("\n"); // preserve line numbers + + } else if (trimmed.startsWith("//#end")) { + if (sinceLastRepeat == null) { err.add(new Warning("#end orphaned")); continue PROCESS; } + Hashtable save = replace; + replace = repeatreplace; + out.print("\n"); + for(int i=0; i= s.length()) return -1; + for (; beginIndex < s.length(); beginIndex++) { + if (s.charAt(beginIndex) == ' ') return beginIndex; + } + return s.length(); + } + + private static int indexOfNotWS(String s) { return indexOfWS(s, 0); } + private static int indexOfNotWS(String s, int beginIndex) { + if (s == null || beginIndex >= s.length()) return -1; + for (; beginIndex < s.length(); beginIndex++) { + if (s.charAt(beginIndex) != ' ') return beginIndex; + } + return -1; + } + + public class Warning { + protected String msg; + protected int line; + + public Warning() { msg = ""; } + public Warning(String m) { msg = m; if (in != null) line = in.getLineNumber(); } + + public String toString() { return "WARNING Line "+line+": "+msg; } + } + + public class Error extends Warning { + public Error() { super(); } + public Error(String m) { super(m); } + public String toString() { return "ERROR Line "+line+": "+msg; } + } + + public static class JSFunctionMacro { + public String unbound1 = null; + public String unbound2 = null; + public String expression = null; + public String process(String args) { + String bound1 = null; + String bound2 = null; + if (unbound2 == null) { + bound1 = args; + return replaceAll(expression, unbound1, bound1); + } else { + bound1 = args.substring(0, args.indexOf(',')); + bound2 = args.substring(args.indexOf(',') + 1); + return replaceAll(replaceAll(expression, unbound1, bound1), unbound2, bound2); + } + } + } +} + diff --git a/src/org/ibex/util/Queue.java b/src/org/ibex/util/Queue.java new file mode 100644 index 0000000..91b9b29 --- /dev/null +++ b/src/org/ibex/util/Queue.java @@ -0,0 +1,91 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +/** A simple synchronized queue, implemented as an array */ +public class Queue { + + public Queue(int initiallength) { vec = new Object[initiallength]; } + + /** The store */ + private Object[] vec; + + /** The index of the first node in the queue */ + private int first = 0; + + /** The number of elements in the queue; INVARAINT: size <= vec.length */ + private int size = 0; + + /** Grow the queue, if needed */ + private void grow(int newlength) { + Object[] newvec = new Object[newlength]; + if (first + size > vec.length) { + System.arraycopy(vec, first, newvec, 0, vec.length - first); + System.arraycopy(vec, 0, newvec, vec.length - first, size - (vec.length - first)); + } else { + System.arraycopy(vec, first, newvec, 0, size); + } + first = 0; + vec = newvec; + } + + /** The number of elements in the queue */ + public int size() { return size; } + + /** Empties the queue */ + public synchronized void flush() { + first = 0; + size = 0; + for(int i=0; i= vec.length) vec[first + size - vec.length] = o; + else vec[first + size] = o; + size++; + if (size == 1) notify(); + } + + /** Remove and return and element from the queue, blocking if empty. */ + public Object remove() { return remove(true); } + + /** Remove and return an element from the queue, blocking if + block is true and the queue is empty. */ + public synchronized Object remove(boolean block) { + + while (size == 0 && block) { + try { wait(); } catch (InterruptedException e) { } + } + + if (!block && size == 0) return null; + Object ret = vec[first]; + first++; + size--; + if (first >= vec.length) first = 0; + return ret; + } + + /** Returns the top element in the queue without removing it */ + public synchronized Object peek() { + if (size == 0) return null; + return vec[first]; + } + +} diff --git a/src/org/ibex/util/Scheduler.java b/src/org/ibex/util/Scheduler.java new file mode 100644 index 0000000..e4c85fa --- /dev/null +++ b/src/org/ibex/util/Scheduler.java @@ -0,0 +1,94 @@ +// Copyright 2004 Adam Megacz, see the COPYING file for licensing [GPL] +package org.ibex.util; + +import java.io.IOException; + +import org.ibex.js.*; +import org.ibex.util.*; +import org.ibex.graphics.*; +import org.ibex.plat.*; + +/** Implements cooperative multitasking */ +public class Scheduler { + + // Public API Exposed to org.ibex ///////////////////////////////////////////////// + + private static Scheduler singleton; + public static void add(Task t) { Log.debug(Scheduler.class, "scheduling " + t); Scheduler.runnable.append(t); } + public static void init() { if (singleton == null) (singleton = Platform.getScheduler()).run(); } + + private static Task current = null; + + private static volatile boolean rendering = false; + private static volatile boolean again = false; + + /** synchronizd so that we can safely call it from an event-delivery thread, in-context */ + public static void renderAll() { + if (rendering) { again = true; return; } + synchronized(Scheduler.class) { + try { + rendering = true; + do { + // FEATURE: this could be cleaner + again = false; + for(int i=0; i all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +/** Simple implementation of a blocking, counting semaphore. */ +public class Semaphore { + + private int val = 0; + + /** Decrement the counter, blocking if zero. */ + public synchronized void block() { + while(val == 0) { + try { + wait(); + } catch (InterruptedException e) { + } catch (Throwable e) { + if (Log.on) Log.info(this, "Exception in Semaphore.block(); this should never happen"); + if (Log.on) Log.info(this, e); + } + } + val--; + } + + /** Incremenet the counter. */ + public synchronized void release() { + val++; + notify(); + } + +} diff --git a/src/org/ibex/util/Simplex.java b/src/org/ibex/util/Simplex.java new file mode 100644 index 0000000..2ae314a --- /dev/null +++ b/src/org/ibex/util/Simplex.java @@ -0,0 +1,1345 @@ +package org.ibex.util; +import java.io.* ; +import java.util.* ; + +public class Simplex { + + public final static short FAIL = -1; + + public final static short NULL = 0; + public final static short FALSE = 0; + public final static short TRUE = 1; + + public final static short DEFNUMINV = 50; + + /* solve status values */ + public final static short OPTIMAL = 0; + public final static short MILP_FAIL = 1; + public final static short INFEASIBLE = 2; + public final static short UNBOUNDED = 3; + public final static short FAILURE = 4; + public final static short RUNNING = 5; + + /* lag_solve extra status values */ + public final static short FEAS_FOUND = 6; + public final static short NO_FEAS_FOUND = 7; + public final static short BREAK_BB = 8; + + public final static short FIRST_NI = 0; + public final static short RAND_NI = 1; + + public final static short LE = 0; + public final static short EQ = 1; + public final static short GE = 2; + public final static short OF = 3; + + public final static short MAX_WARN_COUNT = 20; + + public final static float DEF_INFINITE = (float)1e24; /* limit for dynamic range */ + public final static float DEF_EPSB = (float)5.01e-7; /* for rounding RHS values to 0 determine + infeasibility basis */ + public final static float DEF_EPSEL = (float)1e-8; /* for rounding other values (vectors) to 0 */ + public final static float DEF_EPSD = (float)1e-6; /* for rounding reduced costs to zero */ + public final static float DEF_EPSILON = (float)1e-3; /* to determine if a float value is integer */ + + public final static float PREJ = (float)1e-3; /* pivot reject (try others first) */ + + public final static int ETA_START_SIZE = 10000; /* start size of array Eta. Realloced if needed */ + + static class Ref { + float value; + public Ref(float v) { value = v; } + } + + //public static class Simplex { + /* Globals used by solver */ + short JustInverted; + short Status; + short Doiter; + short DoInvert; + short Break_bb; + + public short active; /*TRUE if the globals point to this structure*/ + public short debug; /* ## Print B&B information */ + public short trace; /* ## Print information on pivot selection */ + public int rows; /* Nr of constraint rows in the problem */ + int rows_alloc; /* The allocated memory for Rows sized data */ + int columns_alloc; + int sum; /* The size of the variables + the slacks */ + int sum_alloc; + int non_zeros; /* The number of elements in the sparce matrix*/ + int mat_alloc; /* The allocated size for matrix sized + structures */ + MatrixArray mat; /* mat_alloc :The sparse matrix */ + MatrixArray alternate_mat; /* mat_alloc :The sparse matrix */ + int[] col_end; /* columns_alloc+1 :Cend[i] is the index of the + first element after column i. + column[i] is stored in elements + col_end[i-1] to col_end[i]-1 */ + int[] col_no; /* mat_alloc :From Row 1 on, col_no contains the + column nr. of the + nonzero elements, row by row */ + short row_end_valid; /* true if row_end & col_no are valid */ + int[] row_end; /* rows_alloc+1 :row_end[i] is the index of the + first element in Colno after row i */ + float[] orig_rh; /* rows_alloc+1 :The RHS after scaling & sign + changing, but before `Bound transformation' */ + float[] rh; /* rows_alloc+1 :As orig_rh, but after Bound + transformation */ + float[] rhs; /* rows_alloc+1 :The RHS of the curent simplex + tableau */ + float[] orig_upbo; /* sum_alloc+1 :Bound before transformations */ + float[] orig_lowbo; /* " " */ + float[] upbo; /* " " :Upper bound after transformation + & B&B work*/ + float[] lowbo; /* " " :Lower bound after transformation + & B&B work */ + + short basis_valid; /* TRUE is the basis is still valid */ + int[] bas; /* rows_alloc+1 :The basis column list */ + short[] basis; /* sum_alloc+1 : basis[i] is TRUE if the column + is in the basis */ + short[] lower; /* " " :TRUE is the variable is at its + lower bound (or in the basis), it is FALSE + if the variable is at its upper bound */ + + short eta_valid; /* TRUE if current Eta structures are valid */ + int eta_alloc; /* The allocated memory for Eta */ + int eta_size; /* The number of Eta columns */ + int num_inv; /* The number of float pivots */ + int max_num_inv; /* ## The number of float pivots between + reinvertions */ + float[] eta_value; /* eta_alloc :The Structure containing the + values of Eta */ + int[] eta_row_nr; /* " " :The Structure containing the Row + indexes of Eta */ + int[] eta_col_end; /* rows_alloc + MaxNumInv : eta_col_end[i] is + the start index of the next Eta column */ + + short bb_rule; /* what rule for selecting B&B variables */ + + short break_at_int; /* TRUE if stop at first integer better than + break_value */ + float break_value; + + float obj_bound; /* ## Objective function bound for speedup of + B&B */ + int iter; /* The number of iterations in the simplex + solver () */ + int total_iter; /* The total number of iterations (B&B) (ILP)*/ + int max_level; /* The Deepest B&B level of the last solution */ + int total_nodes; /* total number of nodes processed in b&b */ + public float[] solution; /* sum_alloc+1 :The Solution of the last LP, + 0 = The Optimal Value, + 1..rows The Slacks, + rows+1..sum The Variables */ + public float[] best_solution; /* " " :The Best 'Integer' Solution */ + float[] duals; /* rows_alloc+1 :The dual variables of the + last LP */ + + short maximise; /* TRUE if the goal is to maximise the + objective function */ + short floor_first; /* TRUE if B&B does floor bound first */ + short[] ch_sign; /* rows_alloc+1 :TRUE if the Row in the matrix + has changed sign + (a`x > b, x>=0) is translated to + s + -a`x = -b with x>=0, s>=0) */ + + int nr_lagrange; /* Nr. of Langrangian relaxation constraints */ + float[][]lag_row; /* NumLagrange, columns+1:Pointer to pointer of + rows */ + float[] lag_rhs; /* NumLagrange :Pointer to pointer of Rhs */ + float[] lambda; /* NumLagrange :Lambda Values */ + short[] lag_con_type; /* NumLagrange :TRUE if constraint type EQ */ + float lag_bound; /* the lagrangian lower bound */ + + short valid; /* Has this lp pased the 'test' */ + float infinite; /* ## numercal stuff */ + float epsilon; /* ## */ + float epsb; /* ## */ + float epsd; /* ## */ + float epsel; /* ## */ + + int Rows; + int columns; + int Sum; + int Non_zeros; + int Level; + MatrixArray Mat; + int[] Col_no; + int[] Col_end; + int[] Row_end; + float[] Orig_rh; + float[] Rh; + float[] Rhs; + float[] Orig_upbo; + float[] Orig_lowbo; + float[] Upbo; + float[] Lowbo; + int[] Bas; + short[] Basis; + short[] Lower; + int Eta_alloc; + int Eta_size; + float[] Eta_value; + int[] Eta_row_nr; + int[] Eta_col_end; + int Num_inv; + float[] Solution; + public float[] Best_solution; + float Infinite; + float Epsilon; + float Epsb; + float Epsd; + float Epsel; + + float TREJ; + float TINV; + + short Maximise; + short Floor_first; + float Extrad; + + int Warn_count; /* used in CHECK version of rounding macro */ + + public Simplex (int nrows, int ncolumns, int matalloc) { + int nsum; + nsum=nrows+ncolumns; + rows=nrows; + columns=ncolumns; + sum=nsum; + rows_alloc=rows; + columns_alloc=columns; + sum_alloc=sum; + mat_alloc=matalloc; + eta_alloc=10000; + max_num_inv=DEFNUMINV; + col_no = new int[mat_alloc]; + col_end = new int[columns + 1]; + row_end = new int[rows + 1]; + orig_rh = new float[rows + 1]; + rh = new float[rows + 1]; + rhs = new float[rows + 1]; + orig_upbo = new float[sum + 1]; + upbo = new float[sum + 1]; + orig_lowbo = new float[sum + 1]; + lowbo = new float[sum + 1]; + bas = new int[rows+1]; + basis = new short[sum + 1]; + lower = new short[sum + 1]; + eta_value = new float[eta_alloc]; + eta_row_nr = new int[eta_alloc]; + eta_col_end = new int[rows_alloc + max_num_inv]; + solution = new float[sum + 1]; + best_solution = new float[sum + 1]; + duals = new float[rows + 1]; + ch_sign = new short[rows + 1]; + mat = new MatrixArray(mat_alloc); + alternate_mat = new MatrixArray(mat_alloc); + } + + public void init(int ncolumns) { + int nsum; + int nrows = 0; + nsum=nrows+ncolumns; + active=FALSE; + debug=FALSE; + trace=FALSE; + rows=nrows; + columns=ncolumns; + sum=nsum; + obj_bound=DEF_INFINITE; + infinite=DEF_INFINITE; + epsilon=DEF_EPSILON; + epsb=DEF_EPSB; + epsd=DEF_EPSD; + epsel=DEF_EPSEL; + non_zeros=0; + + for(int i = 0; i < col_end.length; i++) col_end[i] = 0; + for(int i = 0; i < rows + 1; i++) row_end[i] = 0; + for(int i = 0; i < rows + 1; i++) orig_rh[i] = 0; + for(int i = 0; i < rows + 1; i++) rh[i] = 0; + for(int i = 0; i < rows + 1; i++) rhs[i] = 0; + for(int i = 0; i <= sum; i++) orig_upbo[i]=infinite; + for(int i = 0; i < sum + 1; i++) upbo[i] = 0; + for(int i = 0; i < sum + 1; i++) orig_lowbo[i] = 0; + for(int i = 0; i < sum + 1; i++) lowbo[i] = 0; + for(int i = 0; i <= rows; i++) bas[i] = 0; + for(int i = 0; i <= sum; i++) basis[i] = 0; + for(int i = 0; i <= rows; i++) { bas[i]=i; basis[i]=TRUE; } + for(int i = rows + 1; i <= sum; i++) basis[i]=FALSE; + for(int i = 0 ; i <= sum; i++) lower[i]=TRUE; + for(int i = 0; i <= sum; i++) solution[i] = 0; + for(int i = 0; i <= sum; i++) best_solution[i] = 0; + for(int i = 0; i <= rows; i++) duals[i] = 0; + for(int i = 0; i <= rows; i++) ch_sign[i] = FALSE; + + row_end_valid=FALSE; + bb_rule=FIRST_NI; + break_at_int=FALSE; + break_value=0; + iter=0; + total_iter=0; + basis_valid=TRUE; + eta_valid=TRUE; + eta_size=0; + nr_lagrange=0; + maximise = FALSE; + floor_first = TRUE; + valid = FALSE; + } + + public void setObjective(float[] row, boolean maximize) { + for(int i=row.length-1; i>0; i--) row[i] = row[i-1]; + row[0] = (float)0.0; + for(int j = 1; j <= columns; j++) { + int Row = 0; + int column = j; + float Value = row[j]; + int elmnr, lastelm; + + if(Row > rows || Row < 0) throw new Error("row out of range"); + if(column > columns || column < 1) throw new Error("column out of range"); + + if (basis[column] == TRUE && Row > 0) basis_valid = FALSE; + eta_valid = FALSE; + elmnr = col_end[column-1]; + while((elmnr < col_end[column]) ? (get_row_nr(mat, elmnr) != Row) : false) elmnr++; + if((elmnr != col_end[column]) ? (get_row_nr(mat, elmnr) == Row) : false ) { + if (ch_sign[Row] != FALSE) set_value(mat, elmnr, -Value); + else set_value(mat, elmnr, Value); + } else { + /* check if more space is needed for matrix */ + if (non_zeros + 1 > mat_alloc) throw new Error("not enough mat space; this should not happen"); + /* Shift the matrix */ + lastelm=non_zeros; + for(int i = lastelm; i > elmnr ; i--) { + set_row_nr(mat,i,get_row_nr(mat,i-1)); + set_value(mat,i,get_value(mat,i-1)); + } + for(int i = column; i <= columns; i++) col_end[i]++; + /* Set new element */ + set_row_nr(mat,elmnr, Row); + if (ch_sign[Row] != FALSE) set_value(mat, elmnr, -Value); + else set_value(mat, elmnr, Value); + row_end_valid=FALSE; + non_zeros++; + if (active != FALSE) Non_zeros=non_zeros; + } + } + if (maximize) { + if (maximise == FALSE) { + for(int i = 0; i < non_zeros; i++) + if(get_row_nr(mat, i)==0) + set_value(mat, i, get_value(mat,i)* (float)-1.0); + eta_valid=FALSE; + } + maximise=TRUE; + ch_sign[0]=TRUE; + if (active != FALSE) Maximise=TRUE; + } else { + if (maximise==TRUE) { + for(int i = 0; i < non_zeros; i++) + if(get_row_nr(mat, i)==0) + set_value(mat, i, get_value(mat,i) * (float)-1.0); + eta_valid=FALSE; + } + maximise=FALSE; + ch_sign[0]=FALSE; + if (active != FALSE) Maximise=FALSE; + } + } + + public void add_constraint(float[] row, short constr_type, float rh) { + for(int i=row.length-1; i>0; i--) row[i] = row[i-1]; + row[0] = (float)0.0; + + MatrixArray newmat; + int elmnr; + int stcol; + + newmat = alternate_mat; + for(int i = 0; i < non_zeros; i++) { set_row_nr(newmat,i, 0); set_value(newmat, i, 0); } + for(int i = 1; i <= columns; i++) if (row[i]!=0) non_zeros++; + if (non_zeros > mat_alloc) throw new Error("not enough mat space; this should not happen"); + rows++; + sum++; + if(rows > rows_alloc) throw new Error("not enough rows; this should never happen"); + if(constr_type==GE) ch_sign[rows] = TRUE; + else ch_sign[rows] = FALSE; + + elmnr = 0; + stcol = 0; + for(int i = 1; i <= columns; i++) { + for(int j = stcol; j < col_end[i]; j++) { + set_row_nr(newmat,elmnr, get_row_nr(mat, j)); + set_value(newmat, elmnr, get_value(mat,j)); + elmnr++; + } + if(((i>=1 && i< columns && row[i]!=0)?TRUE:FALSE) != FALSE) { + if(ch_sign[rows] != FALSE) set_value(newmat, elmnr, -row[i]); + else set_value(newmat, elmnr, row[i]); + set_row_nr(newmat,elmnr, rows); + elmnr++; + } + stcol=col_end[i]; + col_end[i]=elmnr; + } + + alternate_mat = mat; + mat = newmat; + + for(int i = sum ; i > rows; i--) { + orig_upbo[i]=orig_upbo[i-1]; + orig_lowbo[i]=orig_lowbo[i-1]; + basis[i]=basis[i-1]; + lower[i]=lower[i-1]; + } + + for(int i = 1 ; i <= rows; i++) if(bas[i] >= rows) bas[i]++; + + if(constr_type==LE || constr_type==GE) orig_upbo[rows]=infinite; + else if(constr_type==EQ) orig_upbo[rows]=0; + else throw new Error("Wrong constraint type\n"); + orig_lowbo[rows]=0; + + if(constr_type==GE && rh != 0) orig_rh[rows]=-rh; + else orig_rh[rows]=rh; + + row_end_valid=FALSE; + + bas[rows]=rows; + basis[rows]=TRUE; + lower[rows]=TRUE; + + if (active != FALSE) set_globals(); + eta_valid=FALSE; + } + + public void bound_sum(int column1, int column2, float bound, short type, float[] scratch) { + for(int i=0; i columns || column < 1) throw new Error("column out of range"); + if(value < orig_lowbo[rows + column]) throw new Error("UpperBound must be >= lowerBound"); + eta_valid = FALSE; + orig_upbo[rows+column] = value; + } + + public void set_lowbo(int column, float value) { + if(column > columns || column < 1) throw new Error("column out of range"); + if(value > orig_upbo[rows + column]) throw new Error("UpperBound must be >= lowerBound"); + eta_valid = FALSE; + orig_lowbo[rows+column] = value; + } + + public void set_rh(int row, float value) { + if(row > rows || row < 0) throw new Error("Row out of Range"); + if(row == 0) throw new Error("Warning: attempt to set RHS of objective function, ignored"); + if (ch_sign[row] != FALSE) orig_rh[row] = -value; + else orig_rh[row] = value; + eta_valid = FALSE; + } + + public void set_rh_vec(float[] rh) { + for(int i=1; i <= rows; i++) + if (ch_sign[i] != FALSE) orig_rh[i]=-rh[i]; + else orig_rh[i]=rh[i]; + eta_valid=FALSE; + } + + + public void set_constr_type(int row, short con_type) { + if (row > rows || row < 1) throw new Error("Row out of Range"); + switch(con_type) { + case EQ: + orig_upbo[row]=0; + basis_valid=FALSE; + if (ch_sign[row] != FALSE) { + for(int i = 0; i < non_zeros; i++) + if (get_row_nr(mat, i)==row) set_value(mat, i, get_value(mat,i) * (float)-1); + eta_valid=FALSE; + ch_sign[row]=FALSE; + if (orig_rh[row]!=0) orig_rh[row]*=-1; + } + break; + case LE: + orig_upbo[row]=infinite; + basis_valid=FALSE; + if (ch_sign[row] != FALSE) { + for(int i = 0; i < non_zeros; i++) + if (get_row_nr(mat, i)==row) set_value(mat, i, get_value(mat,i) * (float)-1); + eta_valid=FALSE; + ch_sign[row]=FALSE; + if (orig_rh[row]!=0) orig_rh[row]*=-1; + } + break; + case GE: + orig_upbo[row]=infinite; + basis_valid=FALSE; + if (ch_sign[row] == FALSE) { + for(int i = 0; i < non_zeros; i++) + if (get_row_nr(mat, i)==row) set_value(mat, i, get_value(mat,i) * (float)-1); + eta_valid=FALSE; + ch_sign[row]=TRUE; + if (orig_rh[row]!=0) orig_rh[row]*=-1; + } + break; + default: throw new Error("Constraint type not (yet) implemented"); + } + } + + void set_globals() { + Rows = rows; + columns = columns; + Sum = Rows + columns; + Non_zeros = non_zeros; + Mat = mat; + Col_no = col_no; + Col_end = col_end; + Row_end = row_end; + Rh = rh; + Rhs = rhs; + Orig_rh = orig_rh; + Orig_upbo = orig_upbo; + Orig_lowbo = orig_lowbo; + Upbo = upbo; + Lowbo = lowbo; + Bas = bas; + Basis = basis; + Lower = lower; + Eta_alloc = eta_alloc; + Eta_size = eta_size; + Num_inv = num_inv; + Eta_value = eta_value; + Eta_row_nr = eta_row_nr; + Eta_col_end = eta_col_end; + Solution = solution; + Best_solution = best_solution; + Infinite = infinite; + Epsilon = epsilon; + Epsb = epsb; + Epsd = epsd; + Epsel = epsel; + TREJ = TREJ; + TINV = TINV; + Maximise = maximise; + Floor_first = floor_first; + active = TRUE; + } + + private void ftran(int start, int end, float[] pcol) { + int k, r; + float theta; + for(int i = start; i <= end; i++) { + k = Eta_col_end[i] - 1; + r = Eta_row_nr[k]; + theta = pcol[r]; + if (theta != 0) for(int j = Eta_col_end[i - 1]; j < k; j++) + pcol[Eta_row_nr[j]] += theta * Eta_value[j]; + pcol[r] *= Eta_value[k]; + } + for(int i = 0; i <= Rows; i++) round(pcol[i], Epsel); + } + + private void btran(float[] row) { + int k; + float f; + for(int i = Eta_size; i >= 1; i--) { + f = 0; + k = Eta_col_end[i] - 1; + for(int j = Eta_col_end[i - 1]; j <= k; j++) f += row[Eta_row_nr[j]] * Eta_value[j]; + f = round(f, Epsel); + row[Eta_row_nr[k]] = f; + } + } + + static int[] num = new int[65535]; + static int[] rownum = new int[65535]; + static int[] colnum = new int[65535]; + + short Isvalid() { + int row_nr; + if (row_end_valid == FALSE) { + for(int i = 0; i <= rows; i++) { num[i] = 0; rownum[i] = 0; } + for(int i = 0; i < non_zeros; i++) rownum[get_row_nr(mat, i)]++; + row_end[0] = 0; + for(int i = 1; i <= rows; i++) row_end[i] = row_end[i - 1] + rownum[i]; + for(int i = 1; i <= columns; i++) + for(int j = col_end[i - 1]; j < col_end[i]; j++) { + row_nr = get_row_nr(mat, j); + if (row_nr != 0) { + num[row_nr]++; + col_no[row_end[row_nr - 1] + num[row_nr]] = i; + } + } + row_end_valid = TRUE; + } + if (valid != FALSE) return(TRUE); + for(int i = 0; i <= rows; i++) rownum[i] = 0; + for(int i = 0; i <= columns; i++) colnum[i] = 0; + for(int i = 1 ; i <= columns; i++) + for(int j = col_end[i - 1]; j < col_end[i]; j++) { + colnum[i]++; + rownum[get_row_nr(mat, j)]++; + } + for(int i = 1; i <= columns; i++) + if (colnum[i] == 0) + throw new Error("Warning: Variable " + i + " not used in any constaints\n"); + valid = TRUE; + return(TRUE); + } + + private void resize_eta() { + Eta_alloc *= 2; + throw new Error("eta undersized; this should never happen"); + /* + float[] db_ptr = Eta_value; + Eta_value = new float[Eta_alloc]; + System.arraycopy(db_ptr, 0, Eta_value, 0, db_ptr.length); + eta_value = Eta_value; + + int[] int_ptr = Eta_row_nr; + Eta_row_nr = new int[Eta_alloc]; + System.arraycopy(int_ptr, 0, Eta_row_nr, 0, int_ptr.length); + eta_row_nr = Eta_row_nr; + */ + } + + private void condensecol(int row_nr, float[] pcol) { + int elnr; + elnr = Eta_col_end[Eta_size]; + if (elnr + Rows + 2 > Eta_alloc) resize_eta(); + for(int i = 0; i <= Rows; i++) + if (i != row_nr && pcol[i] != 0) { + Eta_row_nr[elnr] = i; + Eta_value[elnr] = pcol[i]; + elnr++; + } + Eta_row_nr[elnr] = row_nr; + Eta_value[elnr] = pcol[row_nr]; + elnr++; + Eta_col_end[Eta_size + 1] = elnr; + } + + private void addetacol() { + int k; + float theta; + int j = Eta_col_end[Eta_size]; + Eta_size++; + k = Eta_col_end[Eta_size]; + theta = 1 / (float) Eta_value[k - 1]; + Eta_value[k - 1] = theta; + for(int i = j; i < k - 1; i++) Eta_value[i] *= -theta; + JustInverted = FALSE; + } + + private void setpivcol(short lower, int varin, float[] pcol) { + int colnr; + float f; + if (lower != FALSE) f = 1; + else f = -1; + for(int i = 0; i <= Rows; i++) pcol[i] = 0; + if (varin > Rows) { + colnr = varin - Rows; + for(int i = Col_end[colnr - 1]; i < Col_end[colnr]; i++) pcol[get_row_nr(Mat, i)] = get_value(Mat,i) * f; + pcol[0] -= Extrad * f; + } else { + if (lower != FALSE) pcol[varin] = 1; + else pcol[varin] = -1; + } + ftran(1, Eta_size, pcol); + } + + private void minoriteration(int colnr, int row_nr) { + int k, wk, varin, varout, elnr; + float piv = 0, theta; + varin = colnr + Rows; + elnr = Eta_col_end[Eta_size]; + wk = elnr; + Eta_size++; + if (Extrad != 0) { + Eta_row_nr[elnr] = 0; + Eta_value[elnr] = -Extrad; + elnr++; + } + for(int j = Col_end[colnr - 1] ; j < Col_end[colnr]; j++) { + k = get_row_nr(Mat, j); + if (k == 0 && Extrad != 0) Eta_value[Eta_col_end[Eta_size -1]] += get_value(Mat,j); + else if (k != row_nr) { + Eta_row_nr[elnr] = k; + Eta_value[elnr] = get_value(Mat,j); + elnr++; + } else { + piv = get_value(Mat,j); + } + } + Eta_row_nr[elnr] = row_nr; + Eta_value[elnr] = 1 / (float) piv; + elnr++; + theta = Rhs[row_nr] / (float) piv; + Rhs[row_nr] = theta; + for(int i = wk; i < elnr - 1; i++) Rhs[Eta_row_nr[i]] -= theta * Eta_value[i]; + varout = Bas[row_nr]; + Bas[row_nr] = varin; + Basis[varout] = FALSE; + Basis[varin] = TRUE; + for(int i = wk; i < elnr - 1; i++) Eta_value[i] /= - (float) piv; + Eta_col_end[Eta_size] = elnr; + } + + private void rhsmincol(float theta, int row_nr, int varin) { + int varout; + float f; + if (row_nr > Rows + 1) { + System.err.println("Error: rhsmincol called with row_nr: " + row_nr + ", rows: " + Rows + "\n"); + System.err.println("This indicates numerical instability\n"); + } + int j = Eta_col_end[Eta_size]; + int k = Eta_col_end[Eta_size + 1]; + for(int i = j; i < k; i++) { + f = Rhs[Eta_row_nr[i]] - theta * Eta_value[i]; + f = round(f, Epsb); + Rhs[Eta_row_nr[i]] = f; + } + Rhs[row_nr] = theta; + varout = Bas[row_nr]; + Bas[row_nr] = varin; + Basis[varout] = FALSE; + Basis[varin] = TRUE; + } + + private static int[] rownum_ = new int[65535]; + private static int[] colnum_ = new int[65535]; + private static int[] col = new int[65535]; + private static int[] row = new int[65535]; + private static float[] pcol = new float[65535]; + private static short[] frow = new short[65535]; + private static short[] fcol = new short[65535]; + + void invert() { + int v, wk, numit, varnr, row_nr, colnr, varin; + float theta; + + for(int i = 0; i <= Rows; i++) rownum_[i] = 0; + for(int i = 0; i <= Rows; i++) col[i] = 0; + for(int i = 0; i <= Rows; i++) row[i] = 0; + for(int i = 0; i <= Rows; i++) pcol[i] = 0; + for(int i = 0; i <= Rows; i++) frow[i] = TRUE; + for(int i = 0; i < columns; i++) fcol[i] = FALSE; + for(int i = 0; i <= columns; i++) colnum_[i] = 0; + + for(int i = 0; i <= Rows; i++) + if (Bas[i] > Rows) fcol[Bas[i] - Rows - 1] = TRUE; + else frow[Bas[i]] = FALSE; + + for(int i = 1; i <= Rows; i++) + if (frow[i] != FALSE) + for(int j = Row_end[i - 1] + 1; j <= Row_end[i]; j++) { + wk = Col_no[j]; + if (fcol[wk - 1] != FALSE) { + colnum_[wk]++; + rownum_[i - 1]++; + } + } + + for(int i = 1; i <= Rows; i++) Bas[i] = i; + for(int i = 1; i <= Rows; i++) Basis[i] = TRUE; + for(int i = 1; i <= columns; i++) Basis[i + Rows] = FALSE; + for(int i = 0; i <= Rows; i++) Rhs[i] = Rh[i]; + for(int i = 1; i <= columns; i++) { + varnr = Rows + i; + if (Lower[varnr] == FALSE) { + theta = Upbo[varnr]; + for(int j = Col_end[i - 1]; j < Col_end[i]; j++) + Rhs[get_row_nr(Mat, j)] -= theta * get_value(Mat,j); + } + } + for(int i = 1; i <= Rows; i++) if (Lower[i] == FALSE) Rhs[i] -= Upbo[i]; + Eta_size = 0; + v = 0; + row_nr = 0; + Num_inv = 0; + numit = 0; + while(v < Rows) { + int j; + row_nr++; + if (row_nr > Rows) row_nr = 1; + v++; + if (rownum_[row_nr - 1] == 1) + if (frow[row_nr] != FALSE) { + v = 0; + j = Row_end[row_nr - 1] + 1; + while(fcol[Col_no[j] - 1] == FALSE) j++; + colnr = Col_no[j]; + fcol[colnr - 1] = FALSE; + colnum_[colnr] = 0; + for(j = Col_end[colnr - 1]; j < Col_end[colnr]; j++) + if (frow[get_row_nr(Mat, j)] != FALSE) + rownum_[get_row_nr(Mat, j) - 1]--; + frow[row_nr] = FALSE; + minoriteration(colnr, row_nr); + } + } + v = 0; + colnr = 0; + while(v < columns) { + int j; + colnr++; + if (colnr > columns) colnr = 1; + v++; + if (colnum_[colnr] == 1) + if (fcol[colnr - 1] != FALSE) { + v = 0; + j = Col_end[colnr - 1] + 1; + while(frow[get_row_nr(Mat, j - 1)] == FALSE) j++; + row_nr = get_row_nr(Mat, j - 1); + frow[row_nr] = FALSE; + rownum_[row_nr - 1] = 0; + for(j = Row_end[row_nr - 1] + 1; j <= Row_end[row_nr]; j++) + if (fcol[Col_no[j] - 1] != FALSE) + colnum_[Col_no[j]]--; + fcol[colnr - 1] = FALSE; + numit++; + col[numit - 1] = colnr; + row[numit - 1] = row_nr; + } + } + for(int j = 1; j <= columns; j++) + if (fcol[j - 1] != FALSE) { + fcol[j - 1] = FALSE; + setpivcol(Lower[Rows + j], j + Rows, pcol); + row_nr = 1; + while((frow[row_nr] == FALSE || pcol[row_nr] == FALSE) && row_nr <= Rows) + row_nr++; /* this sometimes sets row_nr to Rows + 1 and makes + rhsmincol crash. Solved in 2.0? MB */ + if (row_nr == Rows + 1) throw new Error("Inverting failed"); + frow[row_nr] = FALSE; + condensecol(row_nr, pcol); + theta = Rhs[row_nr] / (float) pcol[row_nr]; + rhsmincol(theta, row_nr, Rows + j); + addetacol(); + } + for(int i = numit - 1; i >= 0; i--) { + colnr = col[i]; + row_nr = row[i]; + varin = colnr + Rows; + for(int j = 0; j <= Rows; j++) pcol[j] = 0; + for(int j = Col_end[colnr - 1]; j < Col_end[colnr]; j++) pcol[get_row_nr(Mat, j)] = get_value(Mat,j); + pcol[0] -= Extrad; + condensecol(row_nr, pcol); + theta = Rhs[row_nr] / (float) pcol[row_nr]; + rhsmincol(theta, row_nr, varin); + addetacol(); + } + for(int i = 1; i <= Rows; i++) Rhs[i] = round(Rhs[i], Epsb); + JustInverted = TRUE; + DoInvert = FALSE; + } + + private short colprim(Ref colnr, short minit, float[] drow) { + int varnr; + float f, dpiv; + dpiv = -Epsd; + colnr.value = 0; + if (minit == FALSE) { + for(int i = 1; i <= Sum; i++) drow[i] = 0; + drow[0] = 1; + btran(drow); + for(int i = 1; i <= columns; i++) { + varnr = Rows + i; + if (Basis[varnr] == FALSE) + if (Upbo[varnr] > 0) { + f = 0; + for(int j = Col_end[i - 1]; j < Col_end[i]; j++) f += drow[get_row_nr(Mat, j)] * get_value(Mat,j); + drow[varnr] = f; + } + } + for(int i = 1; i <= Sum; i++) drow[i] = round(drow[i], Epsd); + } + for(int i = 1; i <= Sum; i++) + if (Basis[i] == FALSE) + if (Upbo[i] > 0) { + if (Lower[i] != FALSE) f = drow[i]; + else f = -drow[i]; + if (f < dpiv) { + dpiv = f; + colnr.value = i; + } + } + if (colnr.value == 0) { + Doiter = FALSE; + DoInvert = FALSE; + Status = OPTIMAL; + } + return(colnr.value > 0 ? (short)1 : (short)0); + } + + private short rowprim(int colnr, Ref row_nr, Ref theta, float[] pcol) { + float f = 0, quot; + row_nr.value = 0; + theta.value = Infinite; + for(int i = 1; i <= Rows; i++) { + f = pcol[i]; + if (Math.abs(f) < TREJ) f = 0; + if (f != 0) { + quot = 2 * Infinite; + if (f > 0) quot = Rhs[i] / (float) f; + else if (Upbo[Bas[i]] < Infinite) quot = (Rhs[i] - Upbo[Bas[i]]) / (float) f; + round(quot, Epsel); + if (quot < theta.value) { + theta.value = quot; + row_nr.value = i; + } + } + } + if (row_nr.value == 0) + for(int i = 1; i <= Rows; i++) { + f = pcol[i]; + if (f != 0) { + quot = 2 * Infinite; + if (f > 0) quot = Rhs[i] / (float) f; + else if (Upbo[Bas[i]] < Infinite) quot = (Rhs[i] - Upbo[Bas[i]]) / (float) f; + quot = round(quot, Epsel); + if (quot < theta.value) { + theta.value = quot; + row_nr.value = i; + } + } + } + + if (theta.value < 0) throw new Error("Warning: Numerical instability, qout = " + theta.value); + if (row_nr.value == 0) { + if (Upbo[colnr] == Infinite) { + Doiter = FALSE; + DoInvert = FALSE; + Status = UNBOUNDED; + } else { + int i = 1; + while(pcol[i] >= 0 && i <= Rows) i++; + if (i > Rows) { + Lower[colnr] = FALSE; + Rhs[0] += Upbo[colnr]*pcol[0]; + Doiter = FALSE; + DoInvert = FALSE; + } else if (pcol[i]<0) { + row_nr.value = i; + } + } + } + if (row_nr.value > 0) Doiter = TRUE; + return((row_nr.value > 0) ? (short)1 : (short)0); + } + + private short rowdual(Ref row_nr) { + int i; + float f, g, minrhs; + short artifs; + row_nr.value = 0; + minrhs = -Epsb; + i = 0; + artifs = FALSE; + while(i < Rows && artifs == FALSE) { + i++; + f = Upbo[Bas[i]]; + if (f == 0 && (Rhs[i] != 0)) { + artifs = TRUE; + row_nr.value = i; + } else { + if (Rhs[i] < f - Rhs[i]) g = Rhs[i]; + else g = f - Rhs[i]; + if (g < minrhs) { + minrhs = g; + row_nr.value = i; + } + } + } + return(row_nr.value > 0 ? (short)1 : (short)0); + } + + private short coldual(int row_nr, Ref colnr, short minit, float[] prow, float[] drow) { + int r, varnr; + float theta, quot, pivot, d, f, g; + Doiter = FALSE; + if (minit == FALSE) { + for(int i = 0; i <= Rows; i++) { + prow[i] = 0; + drow[i] = 0; + } + drow[0] = 1; + prow[row_nr] = 1; + for(int i = Eta_size; i >= 1; i--) { + d = 0; + f = 0; + r = Eta_row_nr[Eta_col_end[i] - 1]; + for(int j = Eta_col_end[i - 1]; j < Eta_col_end[i]; j++) { + /* this is where the program consumes most cpu time */ + f += prow[Eta_row_nr[j]] * Eta_value[j]; + d += drow[Eta_row_nr[j]] * Eta_value[j]; + } + f = round(f, Epsel); + prow[r] = f; + d = round(d, Epsel); + drow[r] = d; + } + for(int i = 1; i <= columns; i++) { + varnr = Rows + i; + if (Basis[varnr] == FALSE) { + d = - Extrad * drow[0]; + f = 0; + for(int j = Col_end[i - 1]; j < Col_end[i]; j++) { + d = d + drow[get_row_nr(Mat, j)] * get_value(Mat,j); + f = f + prow[get_row_nr(Mat, j)] * get_value(Mat,j); + } + drow[varnr] = d; + prow[varnr] = f; + } + } + for(int i = 0; i <= Sum; i++) { + prow[i] = round(prow[i], Epsel); + drow[i] = round(drow[i], Epsd); + } + } + if (Rhs[row_nr] > Upbo[Bas[row_nr]]) g = -1; + else g = 1; + pivot = 0; + colnr.value = 0; + theta = Infinite; + for(int i = 1; i <= Sum; i++) { + if (Lower[i] != FALSE) d = prow[i] * g; + else d = -prow[i] * g; + if ((d < 0) && (Basis[i] == FALSE) && (Upbo[i] > 0)) { + if (Lower[i] == FALSE) quot = -drow[i] / (float) d; + else quot = drow[i] / (float) d; + if (quot < theta) { + theta = quot; + pivot = d; + colnr.value = i; + } else if ((quot == theta) && (Math.abs(d) > Math.abs(pivot))) { + pivot = d; + colnr.value = i; + } + } + } + if (colnr.value > 0) Doiter = TRUE; + return(colnr.value > 0 ? (short)1 : (short)0); + } + + private void iteration(int row_nr, int varin, Ref theta, float up, Ref minit, Ref low, short primal,float[] pcol) { + int k, varout; + float f; + float pivot; + iter++; + minit.value = theta.value > (up + Epsb) ? 1 : 0; + if (minit.value != 0) { + theta.value = up; + low.value = low.value == 0 ? 1 : 0; + } + k = Eta_col_end[Eta_size + 1]; + pivot = Eta_value[k - 1]; + for(int i = Eta_col_end[Eta_size]; i < k; i++) { + f = Rhs[Eta_row_nr[i]] - theta.value * Eta_value[i]; + f = round(f, Epsb); + Rhs[Eta_row_nr[i]] = f; + } + if (minit.value == 0) { + Rhs[row_nr] = theta.value; + varout = Bas[row_nr]; + Bas[row_nr] = varin; + Basis[varout] = FALSE; + Basis[varin] = TRUE; + if (primal != FALSE && pivot < 0) Lower[varout] = FALSE; + if (low.value == 0 && up < Infinite) { + low.value = TRUE; + Rhs[row_nr] = up - Rhs[row_nr]; + for(int i = Eta_col_end[Eta_size]; i < k; i++) Eta_value[i] = -Eta_value[i]; + } + addetacol(); + Num_inv++; + } + } + + static float[] drow = new float[65535]; + static float[] prow = new float[65535]; + static float[] Pcol = new float[65535]; + + private int solvelp() { + int varnr; + float f = 0, theta = 0; + short primal; + short minit; + int colnr, row_nr; + colnr = 0; + row_nr = 0; + short flag; + Ref ref1, ref2, ref3; + ref1 = new Ref(0); + ref2 = new Ref(0); + ref3 = new Ref(0); + + for(int i = 0; i <= Sum; i++) { drow[i] = 0; prow[i] = 0; } + for(int i = 0; i <= Rows; i++) Pcol[i] = 0; + iter = 0; + minit = FALSE; + Status = RUNNING; + DoInvert = FALSE; + Doiter = FALSE; + primal = TRUE; + for(int i = 0; i != Rows && primal != FALSE;) { + i++; + primal = (Rhs[i] >= 0 && Rhs[i] <= Upbo[Bas[i]]) ? (short)1: (short)0; + } + if (primal == FALSE) { + drow[0] = 1; + for(int i = 1; i <= Rows; i++) drow[i] = 0; + Extrad = 0; + for(int i = 1; i <= columns; i++) { + varnr = Rows + i; + drow[varnr] = 0; + for(int j = Col_end[i - 1]; j < Col_end[i]; j++) + if (drow[get_row_nr(Mat, j)] != 0) + drow[varnr] += drow[get_row_nr(Mat, j)] * get_value(Mat,j); + if (drow[varnr] < Extrad) Extrad = drow[varnr]; + } + } else { + Extrad = 0; + } + minit = FALSE; + while(Status == RUNNING) { + Doiter = FALSE; + DoInvert = FALSE; + construct_solution(Solution); + if (primal != FALSE) { + ref1.value = colnr; + flag = colprim(ref1, minit, drow); + colnr = (int)ref1.value; + if (flag != FALSE) { + setpivcol(Lower[colnr], colnr, Pcol); + ref1.value = row_nr; + ref2.value = theta; + flag = rowprim(colnr, ref1, ref2, Pcol); + row_nr = (int)ref1.value; + theta = ref2.value; + if (flag != FALSE) condensecol(row_nr, Pcol); + } + } else { + if (minit == FALSE) { + ref1.value = row_nr; + flag = rowdual(ref1); + row_nr = (int)ref1.value; + } + if (row_nr > 0) { + ref1.value = colnr; + flag = coldual(row_nr, ref1, minit, prow, drow); + colnr = (int)ref1.value; + if (flag != FALSE) { + setpivcol(Lower[colnr], colnr, Pcol); + /* getting div by zero here ... MB */ + if (Pcol[row_nr] == 0) { + throw new Error("An attempt was made to divide by zero (Pcol[" + row_nr + "])"); + } else { + condensecol(row_nr, Pcol); + f = Rhs[row_nr] - Upbo[Bas[row_nr]]; + if (f > 0) { + theta = f / (float) Pcol[row_nr]; + if (theta <= Upbo[colnr]) + Lower[Bas[row_nr]] = (Lower[Bas[row_nr]] == FALSE)? (short)1:(short)0; + } else theta = Rhs[row_nr] / (float) Pcol[row_nr]; + } + } else Status = INFEASIBLE; + } else { + primal = TRUE; + Doiter = FALSE; + Extrad = 0; + DoInvert = TRUE; + } + } + if (Doiter != FALSE) { + ref1.value = theta; + ref2.value = minit; + ref3.value = Lower[colnr]; + iteration(row_nr, colnr, ref1, Upbo[colnr], ref2, ref3, primal, Pcol); + theta = ref1.value; + minit = (short)ref2.value; + Lower[colnr] = (short)ref3.value; + } + if (Num_inv >= max_num_inv) DoInvert = TRUE; + if (DoInvert != FALSE) invert(); + } + total_iter += iter; + return(Status); + } + + private void construct_solution(float[] sol) { + float f; + int basi; + for(int i = 0; i <= Rows; i++) sol[i] = 0; + for(int i = Rows + 1; i <= Sum; i++) sol[i] = Lowbo[i]; + for(int i = 1; i <= Rows; i++) { + basi = Bas[i]; + if (basi > Rows) sol[basi] += Rhs[i]; + } + for(int i = Rows + 1; i <= Sum; i++) + if (Basis[i] == FALSE && Lower[i] == FALSE) + sol[i] += Upbo[i]; + for(int j = 1; j <= columns; j++) { + f = sol[Rows + j]; + if (f != 0) + for(int i = Col_end[j - 1]; i < Col_end[j]; i++) + sol[get_row_nr(Mat, i)] += f * get_value(Mat,i); + } + for(int i = 0; i <= Rows; i++) { + if (Math.abs(sol[i]) < Epsb) sol[i] = 0; + else if (ch_sign[i] != FALSE) sol[i] = -sol[i]; + } + } + + private void calculate_duals() { + for(int i = 1; i <= Rows; i++) duals[i] = 0; + duals[0] = 1; + btran(duals); + for(int i = 1; i <= Rows; i++) { + if (basis[i] != FALSE) duals[i] = 0; + else if ( ch_sign[0] == ch_sign[i]) duals[i] = -duals[i]; + } + } + + private static Random rdm = new Random(); + + private int milpsolve(float[] upbo, float[] lowbo, short[] sbasis, short[] slower, int[] sbas) { + int failure, notint, is_worse; + float theta, tmpfloat; + notint = 0; + + if (Break_bb != FALSE) return(BREAK_BB); + Level++; + total_nodes++; + if (Level > max_level) max_level = Level; + System.arraycopy(upbo, 0, Upbo, 0, Sum + 1); + System.arraycopy(lowbo, 0, Lowbo, 0, Sum + 1); + System.arraycopy(sbasis, 0, Basis, 0, Sum + 1); + System.arraycopy(slower, 0, Lower, 0, Sum + 1); + System.arraycopy(sbas, 0, Bas, 0, Rows + 1); + System.arraycopy(Orig_rh, 0, Rh, 0, Rows + 1); + if (eta_valid == FALSE) { + for(int i = 1; i <= columns; i++) + if (Lowbo[Rows + i] != 0) { + theta = Lowbo[ Rows + i]; + if (Upbo[Rows + i]= Best_solution[0]) ? 1:0; + if (is_worse != FALSE) { + Level--; + return(MILP_FAIL); + } + /* check if solution contains enough ints */ + if (bb_rule == FIRST_NI) { + notint = 0; + int i = Rows + 1; + while(i <= Sum && notint == 0) i++; + } + if (bb_rule == RAND_NI) { + int nr_not_int, select_not_int; + nr_not_int = 0; + for(int i = Rows + 1; i <= Sum; i++) + if (nr_not_int == 0) notint = 0; + else { + select_not_int=(rdm.nextInt() % nr_not_int) + 1; + i = Rows + 1; + while(select_not_int > 0) i++; + notint = i - 1; + } + } + if (notint != FALSE) throw new Error("integer linear programming not supported"); + if (Maximise != FALSE) is_worse = (Solution[0] < Best_solution[0]) ? 1:0; + else is_worse = (Solution[0] > Best_solution[0]) ? 1:0; + if (is_worse == FALSE) { + System.arraycopy(Solution, 0, Best_solution, 0, Sum + 1); + calculate_duals(); + if (break_at_int != FALSE) { + if (Maximise != FALSE && (Best_solution[0] > break_value)) Break_bb = TRUE; + if (Maximise == FALSE && (Best_solution[0] < break_value)) Break_bb = TRUE; + } + } + } + Level--; + return(failure); + } + + public int solve() { + int result = FAILURE; + if (active == FALSE) set_globals(); + total_iter = 0; + max_level = 1; + total_nodes = 0; + if (Isvalid() != FALSE) { + if (Maximise != FALSE && obj_bound == Infinite) Best_solution[0]=-Infinite; + else if (Maximise == FALSE && obj_bound==-Infinite) Best_solution[0] = Infinite; + else Best_solution[0] = obj_bound; + Level = 0; + if (basis_valid == FALSE) { + for(int i = 0; i <= rows; i++) { + basis[i] = TRUE; + bas[i] = i; + } + for(int i = rows+1; i <= sum; i++) basis[i] = FALSE; + for(int i = 0; i <= sum; i++) lower[i] = TRUE; + basis_valid = TRUE; + } + eta_valid = FALSE; + Break_bb = FALSE; + result = milpsolve(Orig_upbo, Orig_lowbo, Basis, Lower, Bas); + eta_size = Eta_size; + eta_alloc = Eta_alloc; + num_inv = Num_inv; + } + for(int i = 0; i < maxmat; i++) { set_row_nr(mat,i, 0); set_value(mat, i, 0); } + for(int i = 0; i < maxmat; i++) col_no[i] = 0; + + // FIXME: not sure about this + for(int i = 0; i < Eta_size; i++) eta_value[i] = 0; + for(int i = 0; i < Eta_size; i++) eta_row_nr[i] = 0; + for(int i = 0; i < Eta_size; i++) eta_col_end[i] = 0; + + maxmat = 0; + return(result); + } + + private int maxmat = 0; + private final static float round( float val, float eps) { return (Math.abs(val) < eps) ? 0 : val; } + int get_row_nr(MatrixArray m, int i) { return m.row_nr[i]; } + void set_row_nr(MatrixArray m, int i, int val) { m.row_nr[i] = val; maxmat = Math.max(i, maxmat); } + float get_value(MatrixArray m, int i) { return m.value[i]; } + void set_value(MatrixArray m, int i, float val) { m.value[i] = val; maxmat = Math.max(i, maxmat); } + public static class MatrixArray { + public int[] row_nr; + public float[] value; + public final int length; + public MatrixArray(int length) { row_nr = new int[length]; value = new float[length]; this.length = length; } + } + +} + diff --git a/src/org/ibex/util/Task.java b/src/org/ibex/util/Task.java new file mode 100644 index 0000000..e710724 --- /dev/null +++ b/src/org/ibex/util/Task.java @@ -0,0 +1,8 @@ +// Copyright 2004 Adam Megacz, see the COPYING file for licensing [GPL] +package org.ibex.util; +import java.io.IOException; +import org.ibex.js.*; + +public interface Task { + public abstract void perform() throws IOException, JSExn; +} diff --git a/src/org/ibex/util/Vec.java b/src/org/ibex/util/Vec.java new file mode 100644 index 0000000..ffe7cfd --- /dev/null +++ b/src/org/ibex/util/Vec.java @@ -0,0 +1,454 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; +import java.io.*; + +/** + * An unsynchronized Vector implementation; same semantics as + * java.util.Vector. Useful for JDK1.1 platforms that don't have + * java.util.ArrayList. + * + * May contain nulls. + * + * @see java.util.Vector + */ +public final class Vec implements Serializable { + + private Object[] store; + private int size = 0; + + public Vec() { this(10); } + public Vec(int i) { store = new Object[i]; } + public Vec(int i, Object[] store) { size = i; this.store = store; } + + private void grow() { grow(store.length * 2); } + private void grow(int newsize) { + Object[] newstore = new Object[newsize]; + System.arraycopy(store, 0, newstore, 0, size); + store = newstore; + } + + public void removeAllElements() { + for(int i=0; i= store.length - 1) grow(); + store[size++] = o; + } + + public Object peek() { + return lastElement(); + } + + public Object elementAt(int i) { + return store[i]; + } + + public Object lastElement() { + if (size == 0) return null; + return store[size - 1]; + } + + public void push(Object o) { addElement(o); } + public Object pop() { + Object ret = lastElement(); + if (size > 0) store[size--] = null; + return ret; + } + + public int size() { return size; } + + public void setSize(int newSize) { + if (newSize < 0) throw new RuntimeException("tried to set size to negative value"); + if (newSize > store.length) grow(newSize * 2); + if (newSize < size) + for(int i=newSize; i= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits"); + for(int j=i; j= size) setSize(i); + store[i] = o; + } + + public void removeElement(Object o) { + int idx = indexOf(o); + if (idx != -1) removeElementAt(idx); + } + + public void insertElementAt(Object o, int at) { + if (size == store.length) grow(); + for(int i=size; i>at; i--) + store[i] = store[i-1]; + store[at] = o; + size++; + } + + public interface CompareFunc { + public int compare(Object a, Object b); + } + + public void sort(CompareFunc c) { + sort(this, null, c, 0, size-1); + } + + public static void sort(Vec a, Vec b, CompareFunc c) { + if (b != null && a.size != b.size) throw new IllegalArgumentException("Vec a and b must be of equal size"); + sort(a, b, c, 0, a.size-1); + } + + private static final void sort(Vec a, Vec b, CompareFunc c, int start, int end) { + Object tmpa, tmpb = null; + if(start >= end) return; + if(end-start <= 6) { + for(int i=start+1;i<=end;i++) { + tmpa = a.store[i]; + if (b != null) tmpb = b.store[i]; + int j; + for(j=i-1;j>=start;j--) { + if(c.compare(a.store[j],tmpa) <= 0) break; + a.store[j+1] = a.store[j]; + if (b != null) b.store[j+1] = b.store[j]; + } + a.store[j+1] = tmpa; + if (b != null) b.store[j+1] = tmpb; + } + return; + } + + Object pivot = a.store[end]; + int lo = start - 1; + int hi = end; + + do { + while(c.compare(a.store[++lo],pivot) < 0) { } + while((hi > lo) && c.compare(a.store[--hi],pivot) > 0) { } + swap(a, lo,hi); + if (b != null) swap(b, lo,hi); + } while(lo < hi); + + swap(a, lo,end); + if (b != null) swap(b, lo,end); + + sort(a, b, c, start, lo-1); + sort(a, b, c, lo+1, end); + } + + private static final void swap(Vec vec, int a, int b) { + if(a != b) { + Object tmp = vec.store[a]; + vec.store[a] = vec.store[b]; + vec.store[b] = tmp; + } + } + + public static final void sortInts(int[] a, int start, int end) { + int tmpa; + if(start >= end) return; + if(end-start <= 6) { + for(int i=start+1;i<=end;i++) { + tmpa = a[i]; + int j; + for(j=i-1;j>=start;j--) { + if(a[j] <= tmpa) break; + a[j+1] = a[j]; + } + a[j+1] = tmpa; + } + return; + } + int pivot = a[end]; + int lo = start - 1; + int hi = end; + do { + while(a[++lo] < pivot) { } + while((hi > lo) && a[--hi] > pivot) { } + swapInts(a, lo, hi); + } while(lo < hi); + swapInts(a, lo, end); + sortInts(a, start, lo-1); + sortInts(a, lo+1, end); + } + private static final void swapInts(int[] vec, int a, int b) { + if(a != b) { + int tmp = vec[a]; + vec[a] = vec[b]; + vec[b] = tmp; + } + } + + + + // just a cut-and-paste copy of Vec with int storage + public static class Int { + private int[] store; + private int size = 0; + + public Int() { this(10); } + public Int(int i) { store = new int[i]; } + public Int(int i, int[] store) { size = i; this.store = store; } + + private void grow() { grow(store.length * 2); } + private void grow(int newsize) { + int[] newstore = new int[newsize]; + System.arraycopy(store, 0, newstore, 0, size); + store = newstore; + } + + public void removeAllElements() { + for(int i=0; i= store.length - 1) grow(); + store[size++] = o; + } + + public int peek() { + return lastElement(); + } + + public int elementAt(int i) { + return store[i]; + } + + public int lastElement() { + if (size == 0) return 0; + return store[size - 1]; + } + + public void push(int o) { addElement(o); } + public int pop() { + int ret = lastElement(); + if (size > 0) store[size--] = 0; + return ret; + } + + public int size() { return size; } + + public void setSize(int newSize) { + if (newSize < 0) throw new RuntimeException("tried to set size to negative value"); + if (newSize > store.length) grow(newSize * 2); + if (newSize < size) + for(int i=newSize; i= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits"); + for(int j=i; j= size) setSize(i); + store[i] = o; + } + + public void removeElement(int o) { + int idx = indexOf(o); + if (idx != -1) removeElementAt(idx); + } + + public void insertElementAt(int o, int at) { + if (size == store.length) grow(); + for(int i=size; i>at; i--) + store[i] = store[i-1]; + store[at] = o; + size++; + } + + public void sort() { sort(this, null, 0, size-1); } + + public static void sort(Vec.Int a, Vec.Int b) { + if (b != null && a.size != b.size) throw new IllegalArgumentException("Vec.Int a and b must be of equal size"); + sort(a, b, 0, a.size-1); + } + + private static final void sort(Vec.Int a, Vec.Int b, int start, int end) { + int tmpa, tmpb = 0; + if(start >= end) return; + if(end-start <= 6) { + for(int i=start+1;i<=end;i++) { + tmpa = a.store[i]; + if (b != null) tmpb = b.store[i]; + int j; + for(j=i-1;j>=start;j--) { + if((a.store[j]-tmpa) <= 0) break; + a.store[j+1] = a.store[j]; + if (b != null) b.store[j+1] = b.store[j]; + } + a.store[j+1] = tmpa; + if (b != null) b.store[j+1] = tmpb; + } + return; + } + + int pivot = a.store[end]; + int lo = start - 1; + int hi = end; + + do { + while((a.store[++lo]-pivot) < 0) { } + while((hi > lo) && (a.store[--hi]-pivot) > 0) { } + swap(a, lo,hi); + if (b != null) swap(b, lo,hi); + } while(lo < hi); + + swap(a, lo,end); + if (b != null) swap(b, lo,end); + + sort(a, b, start, lo-1); + sort(a, b, lo+1, end); + } + + private static final void swap(Vec.Int vec, int a, int b) { + if(a != b) { + int tmp = vec.store[a]; + vec.store[a] = vec.store[b]; + vec.store[b] = tmp; + } + } + + public static final void sortInts(int[] a, int start, int end) { + int tmpa; + if(start >= end) return; + if(end-start <= 6) { + for(int i=start+1;i<=end;i++) { + tmpa = a[i]; + int j; + for(j=i-1;j>=start;j--) { + if(a[j] <= tmpa) break; + a[j+1] = a[j]; + } + a[j+1] = tmpa; + } + return; + } + + int pivot = a[end]; + int lo = start - 1; + int hi = end; + + do { + while(a[++lo] < pivot) { } + while((hi > lo) && a[--hi] > pivot) { } + swapInts(a, lo, hi); + } while(lo < hi); + swapInts(a, lo, end); + sortInts(a, start, lo-1); + sortInts(a, lo+1, end); + } + + private static final void swapInts(int[] vec, int a, int b) { + if(a != b) { + int tmp = vec[a]; + vec[a] = vec[b]; + vec[b] = tmp; + } + } + } + + + + public static final void sortFloats(float[] a, int start, int end) { + float tmpa; + if(start >= end) return; + if(end-start <= 6) { + for(int i=start+1;i<=end;i++) { + tmpa = a[i]; + int j; + for(j=i-1;j>=start;j--) { + if(a[j] <= tmpa) break; + a[j+1] = a[j]; + } + a[j+1] = tmpa; + } + return; + } + float pivot = a[end]; + int lo = start - 1; + int hi = end; + do { + while(a[++lo] < pivot) { } + while((hi > lo) && a[--hi] > pivot) { } + swapFloats(a, lo, hi); + } while(lo < hi); + swapFloats(a, lo, end); + sortFloats(a, start, lo-1); + sortFloats(a, lo+1, end); + } + private static final void swapFloats(float[] vec, int a, int b) { + if(a != b) { + float tmp = vec[a]; + vec[a] = vec[b]; + vec[b] = tmp; + } + } +} diff --git a/src/org/ibex/util/XML.java b/src/org/ibex/util/XML.java new file mode 100644 index 0000000..d0775c7 --- /dev/null +++ b/src/org/ibex/util/XML.java @@ -0,0 +1,1174 @@ +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + +package org.ibex.util; + +import java.io.Reader; +import java.io.IOException; +import java.io.EOFException; + +/** + * An Event-Driving, Non-Validating XML Parser with Namespace support. + * + * A subclass can implement the abstract functions for receiving details + * about an xml file as it is parsed. To initate a parse, use the parse() + * function. + * + *

Implementation Notes

+ *

As the parser traverses into an element, it adds it to the linked list + * called elements. However, elements has been pre-filled + * with instances of the Element inner class. So in the vast majority of + * cases, the pointer current is moved along one, and the values for the + * new element are filled into the current object.

+ * + *

This parser supports all the unicode ranges required by the XML + * Specification. However, it is optimised for well-formed ASCII documents. + * Documents containing unicode Names and Attributes will take much longer + * to process, and invalid documents (badly formed Names or invalid attributes) + * will be run through a test on every single unicode character range before + * being declared invalid.

+ * + *
    + *
  • Each time the buffer offset off is moved, the length + * len must be decreased.
    • + *
  • Each time the buffer length is decreased, it must be checked to make + * sure it is >0.
    • + *
  • error is defined as a Validity Constraint Violation and + * is recoverable
    • + *
  • fatal error is defined as a Well-formedness Constraint + * Violation and is not recoverable
    • + *
+ * + * @author David Crawshaw + * @see XML Specification + * @see XML Namespaces + */ +public abstract class XML +{ + ///////////////////////////////////////////////////////////////////////////////////////////// + // XML Parser + ///////////////////////////////////////////////////////////////////////////////////////////// + + public static final int BUFFER_SIZE = 255; + + /** static pool of XML.Element instances shared by all XML Parsers. */ + private static final Queue elements = new Queue(30); + + private static final char[] single_amp = new char[] { '&' }; + private static final char[] single_apos = new char[] { '\'' }; + private static final char[] single_gt = new char[] { '>' }; + private static final char[] single_lt = new char[] { '<' }; + private static final char[] single_quot = new char[] { '"' }; + + private int line; + private int col; + + private Reader in; + private char[] buf; + private int off; + private int base; // base+off == distance into the stream + private int len; + + private Element current; + + // used in readEntity() to process a single character without creating a new array + private char[] singlechar = new char[1]; + + + public XML() { this(BUFFER_SIZE); } + + public XML(int bSize) { + buf = new char[bSize]; + + current = (Element)elements.remove(false); + if (current == null) current = new Element(); + } + + /** Returns the line number at the beginning of the last process call. */ + public int getLine() { return line; } + + /** Returns the column number at the beginning of the last process call. */ + public int getCol() { return col; } + + /** Returns the global file offset at the beginning of the last process call. */ + public int getGlobalOffset() { return base + off; } + + /** + * Parse given input and call the abstract event functions. + * + * Careful with threading, as this function is not synchronized. + */ + public final void parse(Reader reader) throws IOException, Exn { + in = reader; + off = len = 0; + line = col = 1; + + clear(); // clean up possible mid-way linked-list element + + try { + // process the stream + while (true) { + if (!buffer(1)) { + if (current.qName == null) break; + throw new Exn("reached eof without closing <"+current.qName+"> element", Exn.WFC, getLine(), getCol()); + } + + if (buf[off] == '<') readTag(); + readChars(current.qName != null); + } + } finally { clear(); } // clean up elements + } + + /** remove any leftover elements from the linked list and queue them */ + private final void clear() { + for (Element last = current; current.parent != null; ) { + current = current.parent; + last.clear(); + elements.append(last); + } + current.clear(); + } + + /** reads in a tag. expects buf[off] == '<' */ + private final void readTag() throws IOException, Exn { + // Start Tag '<' Name (S Attribute)* S? '>' + boolean starttag = true; + + // End Tag '' + boolean endtag = false; + + // if (starttag & endtag) then: EmptyElemTag '<' Name (S Attribute)* S? '/>' + + // Position in the name of the ':' namespace prefix + int prefix = -1; + + int namelen = 0; + + col++; off++; len--; + if (!buffer(1)) throw new EOFException("Unexpected EOF processing element tag"); + + // work out what we can from the beginning of the tag + char s = buf[off]; + if (s == '!') { + // definitions here don't necessarily conform to xml spec (as DTDs not yet implemented) + col++; off++; len--; + if (!buffer(4)) throw new EOFException("Unexpected EOF processing ' + readChars(false, "-->", false); + col += 3; off += 3; len -= 3; + break; + + // we don't care about the following definitions + + case 'A': + if (!buffer(7) + || buf[off+1] != 'T' || buf[off+2] != 'T' || buf[off+3] != 'L' + || buf[off+4] != 'I' || buf[off+5] != 'S' || buf[off+6] != 'T') { + bad = true; break; + } + col += 7; off += 7; len -= 7; + + // ATTLIST '') '>' + readChars(false, ">", true); + col++; off++; len--; + break; + case 'D': + if (!buffer(7) + || buf[off+1] != 'O' || buf[off+2] != 'C' || buf[off+3] != 'T' + || buf[off+4] != 'Y' || buf[off+5] != 'P' || buf[off+6] != 'E') { + bad = true; break; + } + col += 7; off += 7; len -= 7; + + // DTD '') '>' + readChars(false, ">", true); + col++; off++; len--; + break; + case 'E': + if (!buffer(7)) { + bad = true; + } else if (buf[off+1] == 'L' && buf[off+2] == 'E' && buf[off+3] == 'M' + && buf[off+4] == 'E' && buf[off+5] == 'N' && buf[off+6] == 'T') { + // ELEMENT '') '>' + readChars(false, ">", true); + col++; off++; len--; + + } else if (buf[off+1] == 'N' && buf[off+2] == 'T' && buf[off+3] == 'I' + && buf[off+4] == 'T' && buf[off+5] == 'Y') { + // ENTITY '') '>' + readChars(false, ">", true); + col++; off++; len--; + + } else { + bad = true; + } + break; + + case 'N': + if (!buffer(8) + || buf[off+1] != 'O' || buf[off+2] != 'T' || buf[off+3] != 'A' || buf[off+4] != 'T' + || buf[off+5] != 'I' || buf[off+6] != 'O' || buf[off+7] != 'N') { + bad = true; break; + } + col += 8; off += 8; len -= 8; + // NOTATION '') '>' + readChars(false, ">", true); + col++; off++; len--; + + break; + default: bad = true; + } + + if (bad) throw new Exn("element tag start character is invalid", Exn.MARKUP, getLine(), getCol()); + + } else if (s == '?') { + // PI (Ignored) '' Char*)) '?>' + col++; off++; len--; + readChars(false, "?>", true); + if (!buffer(2)) throw new EOFException("Unexpected EOF at end of Processing Instruction"); + col += 2; off += 2; len -= 2; + + } else if (s == '[') { + if (!buffer(7) + || buf[off+1] != 'C' || buf[off+2] != 'D' || buf[off+3] != 'A' + || buf[off+4] != 'T' || buf[off+5] != 'A' || buf[off+6] != '[') { + col++; off--; len++; + // Conditional '' Char*)) ']]>' + readChars(false, "]]>", false); + } else { + col += 7; off += 7; len -=7; + // CDATA '' Char*)) ']]>' + readChars(true, "]]>", false); + } + col += 3; off += 3; len -= 3; + } else { + if (s == '/') { + // End Tag '' + starttag = false; + endtag = true; + + col++; off++; len--; + if (!buffer(1)) throw new EOFException("Unexpected EOF processing end tag"); + s = buf[off]; + } + + if (!Name(s)) throw new Exn("invalid starting character in element name", Exn.MARKUP, getLine(), getCol()); + + // find the element name (defined in XML Spec: section 2.3) + for (namelen = 0; ; namelen++) { + if (!buffer(namelen+1)) throw new EOFException("Unexpected EOF in element tag name"); + + s = buf[off+namelen]; + + if (S(s) || s == '>') { + break; + } else if (s == '/') { + endtag = true; + break; + } else if (s == ':' && namelen > 0 && prefix < 1) { + // we have a definition of the prefix range available + prefix = namelen; + } else if (!NameChar(s)) { + throw new Exn("element name contains invalid character", Exn.MARKUP, getLine(), getCol()); + } + } + + // process name (based on calculated region) + if (namelen < 1) throw new Exn("element name is null", Exn.MARKUP, getLine(), getCol()); + + // we have marked out the name region, so turn it into a string and move on + String qName = new String(buf, off, namelen); + + col += namelen; off += namelen; len -= namelen; + + if (starttag) { + // create the in-memory element representation of this beast + // if current.qName == null then this is the root element we're dealing with + if (current.qName != null) { + Element next = (Element)elements.remove(false); + if (next == null) next = new Element(); + //next.clear(); // TODO: remove as elements now checked as they're added to the queue + next.parent = current; + current = next; + } + + current.qName = qName; + + if (prefix > 0) { + current.prefix = current.qName.substring(0, prefix); + current.localName = current.qName.substring(prefix+1); + } else { + current.prefix = null; + current.localName = current.qName; + } + + // process attributes + readWhitespace(); + if (!buffer(1)) throw new EOFException("Unexpected EOF - processing attributes part 1"); + while (buf[off] != '/' && buf[off] != '>') { + readAttribute(); + if (!buffer(1)) throw new EOFException("Unexpected EOF - processing attributes part 2"); + readWhitespace(); + } + + // work out the uri of this element + current.uri = current.getUri(current.getPrefix()); + if (current.getUri().equals("") && current.getPrefix() != null) + current.addError(new Exn("undefined prefix '"+current.getPrefix()+"'", Exn.NC, getLine(), getCol())); + + } else { + // this is an end-of-element tag + if (!qName.equals(current.getQName())) throw new Exn( + "end tag does not line up with start tag <"+current.getQName()+">", Exn.WFC, getLine(), getCol() + ); + } + + // deal with whitespace + readWhitespace(); + + // process tag close + if (!buffer(1)) throw new EOFException("Unexpected EOF before end of tag"); + if (buf[off] == '/') { + endtag = true; + off++; len--; col++; + } + if (!buffer(1)) throw new EOFException("Unexpected EOF before end of endtag"); + if (buf[off] == '>') { + off++; len--; col++; + } else { + throw new Exn("missing '>' character from element '"+qName+"'", Exn.MARKUP, getLine(), getCol()); + } + + // send element signals + if (starttag) startElement(current); + if (endtag) { + endElement(current); + + // we just closed an element, so remove it from the element 'stack' + if (current.getParent() == null) { + // we just finished the root element + current.clear(); + } else { + Element last = current; + current = current.parent; + last.clear(); + elements.append(last); + } + } + } + } + + /** reads in an attribute of an element. expects Name(buf[off]) */ + private final void readAttribute() throws IOException, Exn { + int ref = 0; + int prefix = 0; + String n, v, p, u; // attribute name, value, prefix and uri respectively + n = v = p = u = null; + char s; + + // find the element name (defined in XML Spec: section 2.3) + for (ref= 0; ; ref++) { + if (!buffer(ref+1)) throw new EOFException("Unexpected EOF in read attribute loop part 1"); + + s = buf[off+ref]; + + if (s == '=' || S(s)) { + break; + } else if (s == ':' && ref > 0 && prefix < 1) { + // we have a definition of the prefix range available + prefix = ref+1; + } else if (!NameChar(s)) { + throw new Exn("attribute name contains invalid characters", Exn.MARKUP, getLine(), getCol()); + } + } + + // determine prefix and key name + if (prefix > 0) { + p = new String(buf, off, prefix-1); + col += prefix; off += prefix; len -= prefix; ref -= prefix; + } + n = new String(buf, off, ref); + col += ref; off += ref; len -= ref; + + // find name/value divider ('=') + readWhitespace(); + if (!buffer(1)) throw new EOFException("Unexpected EOF before attribute '=' divider"); + if (buf[off] != '=') throw new Exn("attribute name not followed by '=' sign", Exn.MARKUP, getLine(), getCol()); + + col++; off++; len--; + readWhitespace(); + + if (!buffer(1)) throw new EOFException("Unexpected EOF after attribute '=' divider"); + + char wrap; + if (buf[off] == '\'' || buf[off] == '"') { + wrap = buf[off]; + } else { + throw new Exn("attribute '"+n+"' must have attribute wrapped in ' or \"", Exn.MARKUP, getLine(), getCol()); + } + col++; off++; len--; + + // find the attribute value + attval: for (ref = 0; ; ref++) { + if (!buffer(ref+1)) throw new EOFException("Unexpected EOF in attribute value"); + + if (buf[off+ref] == wrap) { + break attval; + } else if (buf[off+ref] == '<') { + throw new Exn("attribute value for '"+n+"' must not contain '<'", Exn.WFC, getLine(), getCol()); + } + } + + v = new String(buf, off, ref); + col += ref; off += ref; len -= ref; + + // remove end wrapper character + col++; off++; len--; + + // process attribute + if (p != null && p.equals("xmlns")) { + current.addUri(n, v); + } else if (n.equals("xmlns")) { + if (current.getUri().equals("")) { + current.addUri("", v); + } else { + current.addError(new Exn("default namespace definition repeated", Exn.NC, getLine(), getCol())); + } + } else { + // find attribute uri + u = current.getUri(p); + if (p != null && u.equals("")) current.addError(new Exn("undefined attribute prefix '"+p+"'", Exn.NC, getLine(), getCol())); + + // check to see if attribute is a repeat + for (int i=0; current.len > i; i++) if (n.equals(current.getAttrKey(i)) && u.equals(current.getAttrUri(i))) throw new Exn( + "attribute name '"+n+"' may not appear more than once in the same element tag", Exn.WFC, getLine(), getCol() + ); + + current.addAttr(n, v, u); + } + } + + /** reads an entity and processes out its value. expects buf[off] == '&' */ + private final void readEntity() throws IOException, Exn { + off++; len--; + if (!buffer(2)) throw new EOFException("Unexpected EOF reading entity"); + + boolean unknown = false; + switch (buf[off]) { + case '#': + off++; len--; + + int radix; + if (buf[off] == 'x') { off++; len--; radix = 16; } else { radix = 10; } + int c = 0; + + // read in each char, then shift total value to the left and add the extra + // style of loop is slightly different from all the others, as this should run a limited number of times + findchar: while (true) { + if (!buffer(1)) throw new EOFException("Unexpected EOF reading entity"); + int d = Character.digit(buf[off], radix); + if (d == -1) { + if (buf[off] != ';') throw new Exn("illegal characters in entity reference", Exn.WFC, getLine(), getCol()); + off++; len--; col++; + break findchar; + } + c = (c * radix) + d; + + off++; len--; + } + + singlechar[0] = Character.forDigit(c, radix); + characters(singlechar, 0, 1); + break; + + case 'a': + if (buffer(4) && buf[off+1] == 'm' && buf[off+2] == 'p' && buf[off+3] == ';') { + characters(single_amp, 0, 1); // & + off += 4; len -= 4; col++; + } else if (buffer(5) && buf[off+1] == 'p' && buf[off+2] == 'o' && buf[off+3] == 's' && buf[off+4] == ';') { + characters(single_apos, 0, 1); // ' + off += 5; len -= 5; col++; + } else { + unknown = true; + } + break; + + case 'g': + if (buffer(3) && buf[off+1] == 't' && buf[off+2] == ';') { + characters(single_gt, 0, 1); // > + off += 3; len -= 3; col++; + } else { + unknown = true; + } + break; + + case 'l': + if (buffer(3) && buf[off+1] == 't' && buf[off+2] == ';') { + characters(single_lt, 0, 1); // < + off += 3; len -= 3; col++; + } else { + unknown = true; + } + break; + + case 'q': + if (buffer(5) && buf[off+1] == 'u' && buf[off+2] == 'o' && buf[off+3] == 't' && buf[off+4] == ';') { + characters(single_quot, 0, 1); // " + off += 5; len -= 5; col++; + } else { + unknown = true; + } + break; + + // TODO: check a parser-level Hash of defined entities + } + + if (unknown) throw new Exn("unknown entity ( not supported)", Exn.WFC, getLine(), getCol()); + } + + /** reads until the passed string is encountered. */ + private final void readChars(boolean p, String match, boolean entities) throws IOException, Exn { + int ref; + char[] end = match.toCharArray(); + + for (boolean more = true; more;) { + if (!buffer(1)) return; + + buf: for (ref = 0; ref < len; ref++) { + switch (buf[off+ref]) { + case '\r': // windows or macos9 newline + // normalise and process + buf[off+ref] = '\n'; ref++; + if (p) characters(buf, off, ref); + off += ref; len -= ref; ref = -1; + line++; col = 1; + + // windows double-char newline; skip the next char + if (!buffer(1)) return; + if (buf[off] == '\n') { off++; len--; } + break; + + case '\n': // unix newline + ref++; + if (p) characters(buf, off, ref); + off += ref; len -= ref; ref = -1; + line++; col = 1; + break; + + case '&': // entity + if (entities) { + if (p) { + if (ref > 0) characters(buf, off, ref); + off += ref; len -= ref; ref = -1; + readEntity(); + } + break; + } + + default: + if (!buffer(ref+end.length)) continue buf; + for (int i=0; end.length > i; i++) if (end[i] != buf[off+ref+i]) continue buf; + more = false; + break buf; + } + } + + if (p && ref > 0) characters(buf, off, ref); + off += ref; len -= ref; col += ref; + } + } + + /** + * reads until a < symbol is encountered + * @param p If true call the characters(char[],int,int) funciton for the processed characters + */ + private final void readChars(boolean p) throws IOException, Exn { + int ref; + + for (boolean more = true; more;) { + if (!buffer(1)) return; + + buf: for (ref = 0; ref < len; ref++) { + switch (buf[off+ref]) { + case '\r': // windows or macos9 newline + // normalise and process + buf[off+ref] = '\n'; ref++; + if (p) characters(buf, off, ref); + off += ref; len -= ref; ref = -1; + line++; col = 1; + + // windows double-char newline; skip the next char + if (!buffer(1)) return; + if (buf[off] == '\n') { off++; len--; } + break; + + case '\n': // unix newline + ref++; + if (p) characters(buf, off, ref); + off += ref; len -= ref; ref = -1; + line++; col = 1; + break; + + case '&': // entity + if (p) { + if (ref > 0) characters(buf, off, ref); + off += ref; len -= ref; ref = -1; + readEntity(); + } + break; + + case '<': // end of chars section + more = false; + break buf; + } + } + + if (p && ref > 0) characters(buf, off, ref); + off += ref; len -= ref; col += ref; + } + } + + /** reads until a non-whitespace symbol is encountered */ + private final void readWhitespace() throws IOException, Exn { + int ref; + + for (boolean more = true; more;) { + if (!buffer(1)) return; + + buf: for (ref = 0; ref < len; ref++) { + switch (buf[off+ref]) { + case '\r': // windows or macos9 newline + // normalise and process + buf[off+ref] = '\n'; + whitespace(buf, off, ++ref); + off += ref; len -= ref; ref = -1; + line++; col = 1; + + // windows double-char newline; skip the next char + if (!buffer(1)) return; + if (buf[off] == '\n') { off++; len--; } + break; + + case '\n': // unix newline + whitespace(buf, off, ++ref); + off += ref; len -= ref; ref = -1; + line++; col = 1; + break; + + case ' ': // space + case '\t': // tab + break; + + default: // end of whitespace + more = false; + break buf; + } + } + + off += ref; len -= ref; col += ref; + } + } + + /** + * attempt to fill the buffer. + * + * @param min Minimum number of characters to read (even if we have to block to do it). + * @return return false if min can't be reached. + */ + private final boolean buffer(int min) throws IOException { + if (len > min) return true; + + if (buf.length - (off+len) >= min) { + // plenty of space left on the end of the buffer + } else if (off >= min) { + // moving offset data to start will leave enough free space on the end + System.arraycopy(buf, off, buf, 0, len); + base += off; + off = 0; + } else { + // buffer size will have to be increased + char[] newbuf = new char[buf.length * 2]; + System.arraycopy(buf, off, newbuf, 0, len); + buf = newbuf; + base += off; + off = 0; + } + + while (min > len) { + int newlen = in.read(buf, off+len, buf.length-(off+len)); + if (newlen < 0) return false; + len += newlen; + } + + return true; + } + + + ///////////////////////////////////////////////////////////////////////////////////////////// + // Abstract SAX-Like Interface + ///////////////////////////////////////////////////////////////////////////////////////////// + + /** + * Called when the start of an element is processed. + * + *

DO NOT store a reference to the Element object, as + * they are reused by XML Parser.

+ */ + public abstract void startElement(Element e) throws Exn; + + /** + * Represents up to a line of character data. + * + *

Newlines are all normalised to the Unix \n as per the XML Spec, + * and a newline will only appear as the last character in the passed + * array segment.

+ * + *

XML.getLine() and XML.getCol() report the position at the + * beginning of this character segment, which can be processed in a + * line-by-line fashion due to the above newline restriction.

+ */ + public abstract void characters(char[] ch, int start, int length) throws Exn, IOException; + + /** Represents up to a line of ignorable whitespace. */ + public abstract void whitespace(char[] ch, int start, int length) throws Exn, IOException; + + /** Represents the end of an Element. */ + public abstract void endElement(Element e) throws Exn, IOException; + + + ///////////////////////////////////////////////////////////////////////////////////////////// + // Inner Classes for Parser Support + ///////////////////////////////////////////////////////////////////////////////////////////// + + /** + * Represents an element in an XML document. Stores a reference to its + * parent, forming a one-way linked list. + * + * Element objects are reused, so client code making use of them must + * drop their references after the specific element process function + * has returned. + */ + public static final class Element { + + private static final int DEFAULT_ATTR_SIZE = 10; + + protected Element parent = null; + + protected String uri = null; + protected String localName = null; + protected String qName = null; + protected String prefix = null; + + protected Hash urimap = new Hash(3,3); + + protected String[] keys = new String[DEFAULT_ATTR_SIZE]; + protected String[] vals = new String[DEFAULT_ATTR_SIZE]; + protected String[] uris = new String[DEFAULT_ATTR_SIZE]; + protected int len = 0; + + protected Exn[] errors = new Exn[] {}; + + /** Parent of current element. */ + public Element getParent() { return parent; } + + /** Qualified Name of current element. XML Namespace Spec 14-Jan-1999 [6] */ + public String getQName() { return qName; } + + /** LocalPart of current element. XML Namespace Spec 14-Jan-1999 [8] */ + public String getLocalName() { return localName; } + + /** Prefix of current element. Substring of qName. XML Namespace Spec 14-Jan-1999 [7] */ + public String getPrefix() { return prefix; } + + // HACK + public Hash getUriMap() { + Hash map = new Hash(); + for (Element e = this; e != null; e = e.getParent()) { + java.util.Enumeration en = e.urimap.keys(); + while(en.hasMoreElements()) { + String key = (String)en.nextElement(); + String val = getUri(key); + map.put(key, val); + } + } + return map; + } + + /** URI of current tag. XML Namespace Spec 14-Jan-1999 section 1 */ + public String getUri() { return getUri(prefix); } + + /** URI of a given prefix. Never returns null, instead gives "". */ + public String getUri(String p) { + String ret = null; + for (Element e = this; e != null && ret == null; e = e.getParent()) { + ret = (String)e.urimap.get(p == null ? "" : p); + } + return ret == null ? "" : ret; + } + + /** An array of attribute names. */ + public String getAttrKey(int pos) { return len > pos ? keys[pos] : null; } + + /** An array of attribute values. */ + public String getAttrVal(int pos) { return len > pos ? vals[pos] : null; } + + /** An array of attribute uris. */ + public String getAttrUri(int pos) { return len > pos ? uris[pos] : null; } + + /** Current number of attributes in the element. */ + public int getAttrLen() { return len; } + + /** Poor performance, but easier to use when speed is not a concern */ + public Hash getAttrHash() { + Hash ret = new Hash(getAttrLen() * 2, 3); + for(int i=0; i i; i++) { keys[i] = null; vals[i] = null; uris[i] = null; }; + } + len = 0; + + errors = new Exn[] {}; + } + } + + /** Parse or Structural Error */ + public static class Exn extends Exception { + /** Violation of Markup restrictions in XML Specification - Fatal Error */ + public static final int MARKUP = 1; + + /** Well-Formedness Constraint Violation - Fatal Error */ + public static final int WFC = 2; + + /** Namespace Constraint Violation - Recoverable Error */ + public static final int NC = 3; + + /** Schema Violation - Fatal Error */ + public static final int SCHEMA = 4; + + private String error; + private int type; + private int line; + private int col; + + public Exn(String e) { this(e, MARKUP, -1, -1); } + + public Exn(String e, int type, int line, int col) { + this.error = e; + this.type = type; + this.line = line; + this.col = col; + } + + public int getType() { return this.type; } + public int getLine() { return this.line; } + public int getCol() { return this.col; } + public String getMessage() { return this.error + (line >= 0 && col >= 0 ? " at " + line + ":" + col: ""); } + } + + + ///////////////////////////////////////////////////////////////////////////////////////////// + // Static Support Functions for the XML Specification + ///////////////////////////////////////////////////////////////////////////////////////////// + + // attempt to avoid these functions unless you *expect* the input to fall in the given range. + + /** First Character of Name - XML Specification 1.0 [5] */ + private static final boolean Name(char c) { + return BaseCharAscii(c) || c == '_' || c == ':' || Letter(c); + } + + /** NameChar - XML Specification 1.0 [4] */ + private static final boolean NameChar(char c) { + return BaseCharAscii(c) || c == '.' || c == '-' || c == '_' || c == ':' + || Digit(c) || Letter(c) || Extender(c); // TODO: || CombiningChar(c); + } + + /** BaseChar - XMl Specification 1.0 [84] */ + private static final boolean Letter(char c) { + return BaseChar(c) || Ideographic(c); + } + + /** Elements of BaseChar that exist in ASCII. */ + private static final boolean BaseCharAscii(char c) { + return (c >= '\u0041' && c <= '\u005A') || (c >= '\u0061' && c <= '\u007A'); + } + + /** Char - XML Specification 1.0 [2] */ + private static final boolean Char(char c) { + // u000A == r and u000D == n, but the javac compiler can't handle the \ u form + return c == '\u0009' || c == '\r' || c == '\n' + || (c >= '\u0020' && c <= '\uD7FF') + || (c >= '\uE000' && c <= '\uFFFD'); + } + + /** BaseChar - XML Specification 1.0 [85] */ + private static final boolean BaseChar(char c) { + return BaseCharAscii(c) || (c >= '\u00C0' && c <= '\u00D6') + || (c >= '\u00D8' && c <= '\u00F6') || (c >= '\u00F8' && c <= '\u00FF') || (c >= '\u0100' && c <= '\u0131') + || (c >= '\u0134' && c <= '\u013E') || (c >= '\u0141' && c <= '\u0148') || (c >= '\u014A' && c <= '\u017E') + || (c >= '\u0180' && c <= '\u01C3') || (c >= '\u01CD' && c <= '\u01F0') || (c >= '\u01F4' && c <= '\u01F5') + || (c >= '\u01FA' && c <= '\u0217') || (c >= '\u0250' && c <= '\u02A8') || (c >= '\u02BB' && c <= '\u02C1') + || (c == '\u0386') || (c >= '\u0388' && c <= '\u038A') || (c == '\u038C') + || (c >= '\u038E' && c <= '\u03A1') || (c >= '\u03A3' && c <= '\u03CE') || (c >= '\u03D0' && c <= '\u03D6') + || (c == '\u03DA') || (c == '\u03DC') || (c == '\u03DE') + || (c == '\u03E0') + || (c >= '\u03E2' && c <= '\u03F3') || (c >= '\u0401' && c <= '\u040C') || (c >= '\u040E' && c <= '\u044F') + || (c >= '\u0451' && c <= '\u045C') || (c >= '\u045E' && c <= '\u0481') || (c >= '\u0490' && c <= '\u04C4') + || (c >= '\u04C7' && c <= '\u04C8') || (c >= '\u04CB' && c <= '\u04CC') || (c >= '\u04D0' && c <= '\u04EB') + || (c >= '\u04EE' && c <= '\u04F5') || (c >= '\u04F8' && c <= '\u04F9') || (c >= '\u0531' && c <= '\u0556') + || (c == '\u0559') + || (c >= '\u0561' && c <= '\u0586') || (c >= '\u05D0' && c <= '\u05EA') || (c >= '\u05F0' && c <= '\u05F2') + || (c >= '\u0621' && c <= '\u063A') || (c >= '\u0641' && c <= '\u064A') || (c >= '\u0671' && c <= '\u06B7') + || (c >= '\u06BA' && c <= '\u06BE') || (c >= '\u06C0' && c <= '\u06CE') || (c >= '\u06D0' && c <= '\u06D3') + || (c == '\u06D5') + || (c >= '\u06E5' && c <= '\u06E6') || (c >= '\u0905' && c <= '\u0939') + || (c == '\u093D') + || (c >= '\u0958' && c <= '\u0961') || (c >= '\u0985' && c <= '\u098C') || (c >= '\u098F' && c <= '\u0990') + || (c >= '\u0993' && c <= '\u09A8') || (c >= '\u09AA' && c <= '\u09B0') + || (c == '\u09B2') + || (c >= '\u09B6' && c <= '\u09B9') || (c >= '\u09DF' && c <= '\u09E1') || (c >= '\u09F0' && c <= '\u09F1') + || (c >= '\u0A05' && c <= '\u0A0A') || (c >= '\u0A0F' && c <= '\u0A10') || (c >= '\u0A13' && c <= '\u0A28') + || (c >= '\u0A2A' && c <= '\u0A30') || (c >= '\u0A32' && c <= '\u0A33') || (c >= '\u0A35' && c <= '\u0A36') + || (c >= '\u0A38' && c <= '\u0A39') || (c >= '\u0A59' && c <= '\u0A5C') + || (c == '\u0A5E') + || (c >= '\u0A72' && c <= '\u0A74') || (c >= '\u0A85' && c <= '\u0A8B') + || (c == '\u0A8D') + || (c >= '\u0A8F' && c <= '\u0A91') || (c >= '\u0A93' && c <= '\u0AA8') || (c >= '\u0AAA' && c <= '\u0AB0') + || (c >= '\u0AB2' && c <= '\u0AB3') || (c >= '\u0AB5' && c <= '\u0AB9') + || (c == '\u0ABD') + || (c == '\u0AE0') + || (c >= '\u0B05' && c <= '\u0B0C') || (c >= '\u0B0F' && c <= '\u0B10') || (c >= '\u0B13' && c <= '\u0B28') + || (c >= '\u0B2A' && c <= '\u0B30') || (c >= '\u0B32' && c <= '\u0B33') || (c >= '\u0B36' && c <= '\u0B39') + || (c == '\u0B3D') + || (c >= '\u0B5C' && c <= '\u0B5D') || (c >= '\u0B5F' && c <= '\u0B61') || (c >= '\u0B85' && c <= '\u0B8A') + || (c >= '\u0B8E' && c <= '\u0B90') || (c >= '\u0B92' && c <= '\u0B95') || (c >= '\u0B99' && c <= '\u0B9A') + || (c == '\u0B9C') + || (c >= '\u0B9E' && c <= '\u0B9F') || (c >= '\u0BA3' && c <= '\u0BA4') || (c >= '\u0BA8' && c <= '\u0BAA') + || (c >= '\u0BAE' && c <= '\u0BB5') || (c >= '\u0BB7' && c <= '\u0BB9') || (c >= '\u0C05' && c <= '\u0C0C') + || (c >= '\u0C0E' && c <= '\u0C10') || (c >= '\u0C12' && c <= '\u0C28') || (c >= '\u0C2A' && c <= '\u0C33') + || (c >= '\u0C35' && c <= '\u0C39') || (c >= '\u0C60' && c <= '\u0C61') || (c >= '\u0C85' && c <= '\u0C8C') + || (c >= '\u0C8E' && c <= '\u0C90') || (c >= '\u0C92' && c <= '\u0CA8') || (c >= '\u0CAA' && c <= '\u0CB3') + || (c >= '\u0CB5' && c <= '\u0CB9') + || (c == '\u0CDE') + || (c >= '\u0CE0' && c <= '\u0CE1') || (c >= '\u0D05' && c <= '\u0D0C') || (c >= '\u0D0E' && c <= '\u0D10') + || (c >= '\u0D12' && c <= '\u0D28') || (c >= '\u0D2A' && c <= '\u0D39') || (c >= '\u0D60' && c <= '\u0D61') + || (c >= '\u0E01' && c <= '\u0E2E') + || (c == '\u0E30') + || (c >= '\u0E32' && c <= '\u0E33') || (c >= '\u0E40' && c <= '\u0E45') || (c >= '\u0E81' && c <= '\u0E82') + || (c == '\u0E84') + || (c >= '\u0E87' && c <= '\u0E88') + || (c == '\u0E8A') + || (c == '\u0E8D') + || (c >= '\u0E94' && c <= '\u0E97') || (c >= '\u0E99' && c <= '\u0E9F') || (c >= '\u0EA1' && c <= '\u0EA3') + || (c == '\u0EA5') + || (c == '\u0EA7') + || (c >= '\u0EAA' && c <= '\u0EAB') || (c >= '\u0EAD' && c <= '\u0EAE') + || (c == '\u0EB0') + || (c >= '\u0EB2' && c <= '\u0EB3') + || (c == '\u0EBD') + || (c >= '\u0EC0' && c <= '\u0EC4') || (c >= '\u0F40' && c <= '\u0F47') || (c >= '\u0F49' && c <= '\u0F69') + || (c >= '\u10A0' && c <= '\u10C5') || (c >= '\u10D0' && c <= '\u10F6') + || (c == '\u1100') + || (c >= '\u1102' && c <= '\u1103') || (c >= '\u1105' && c <= '\u1107') + || (c == '\u1109') + || (c >= '\u110B' && c <= '\u110C') || (c >= '\u110E' && c <= '\u1112') + || (c == '\u113C') + || (c == '\u113E') + || (c == '\u1140') + || (c == '\u114C') + || (c == '\u114E') + || (c == '\u1150') + || (c >= '\u1154' && c <= '\u1155') + || (c == '\u1159') + || (c >= '\u115F' && c <= '\u1161') + || (c == '\u1163') + || (c == '\u1165') + || (c == '\u1167') + || (c == '\u1169') + || (c >= '\u116D' && c <= '\u116E') || (c >= '\u1172' && c <= '\u1173') + || (c == '\u1175') + || (c == '\u119E') + || (c == '\u11A8') + || (c == '\u11AB') + || (c >= '\u11AE' && c <= '\u11AF') || (c >= '\u11B7' && c <= '\u11B8') + || (c == '\u11BA') + || (c >= '\u11BC' && c <= '\u11C2') + || (c == '\u11EB') + || (c == '\u11F0') + || (c == '\u11F9') + || (c >= '\u1E00' && c <= '\u1E9B') || (c >= '\u1EA0' && c <= '\u1EF9') || (c >= '\u1F00' && c <= '\u1F15') + || (c >= '\u1F18' && c <= '\u1F1D') || (c >= '\u1F20' && c <= '\u1F45') || (c >= '\u1F48' && c <= '\u1F4D') + || (c >= '\u1F50' && c <= '\u1F57') + || (c == '\u1F59') + || (c == '\u1F5B') + || (c == '\u1F5D') + || (c >= '\u1F5F' && c <= '\u1F7D') || (c >= '\u1F80' && c <= '\u1FB4') || (c >= '\u1FB6' && c <= '\u1FBC') + || (c == '\u1FBE') + || (c >= '\u1FC2' && c <= '\u1FC4') || (c >= '\u1FC6' && c <= '\u1FCC') || (c >= '\u1FD0' && c <= '\u1FD3') + || (c >= '\u1FD6' && c <= '\u1FDB') || (c >= '\u1FE0' && c <= '\u1FEC') || (c >= '\u1FF2' && c <= '\u1FF4') + || (c >= '\u1FF6' && c <= '\u1FFC') + || (c == '\u2126') + || (c >= '\u212A' && c <= '\u212B') + || (c == '\u212E') + || (c >= '\u2180' && c <= '\u2182') || (c >= '\u3041' && c <= '\u3094') || (c >= '\u30A1' && c <= '\u30FA') + || (c >= '\u3105' && c <= '\u312C') || (c >= '\uAC00' && c <= '\uD7A3'); + } + + /** BaseChar - XMl Specification 1.0 [86] */ + private static final boolean Ideographic(char c) { + return (c >= '\u4E00' && c <= '\u9FA5') || c == '\u3007' || (c >= '\u3021' && c <= '\u3029'); + } + + /** CombiningChar - XMl Specification 1.0 [87] */ + /*private static final boolean CombiningChar(char c) { + return (c >= '\u0300' && c <= '\u0345') + || (c >= '\u0360' && c <= '\u0361') || (c >= '\u0483' && c <= '\u0486') || (c >= '\u0591' && c <= '\u05A1') + || (c >= '\u05A3' && c <= '\u05B9') || (c >= '\u05BB' && c <= '\u05BD') + || (c == '\u05BF') + || (c >= '\u05C1' && c <= '\u05C2') + || (c == '\u05C4') + || (c >= '\u064B' && c <= '\u0652') + || (c == '\u0670') + || (c >= '\u06D6' && c <= '\u06DC') || (c >= '\u06DD' && c <= '\u06DF') || (c >= '\u06E0' && c <= '\u06E4') + || (c >= '\u06E7' && c <= '\u06E8') || (c >= '\u06EA' && c <= '\u06ED') || (c >= '\u0901' && c <= '\u0903') + || (c == '\u093C') + || (c >= '\u093E' && c <= '\u094C') + || (c == '\u094D') + || (c >= '\u0951' && c <= '\u0954') || (c >= '\u0962' && c <= '\u0963') || (c >= '\u0981' && c <= '\u0983') + || (c == '\u09BC') + || (c == '\u09BE') + || (c == '\u09BF') + || (c >= '\u09C0' && c <= '\u09C4') || (c >= '\u09C7' && c <= '\u09C8') || (c >= '\u09CB' && c <= '\u09CD') + || (c == '\u09D7') + || (c >= '\u09E2' && c <= '\u09E3') + || (c == '\u0A02') + || (c == '\u0A3C') + || (c == '\u0A3E') + || (c == '\u0A3F') + || (c >= '\u0A40' && c <= '\u0A42') || (c >= '\u0A47' && c <= '\u0A48') || (c >= '\u0A4B' && c <= '\u0A4D') + || (c >= '\u0A70' && c <= '\u0A71') || (c >= '\u0A81' && c <= '\u0A83') + || (c == '\u0ABC') + || (c >= '\u0ABE' && c <= '\u0AC5') || (c >= '\u0AC7' && c <= '\u0AC9') || (c >= '\u0ACB' && c <= '\u0ACD') + || (c >= '\u0B01' && c <= '\u0B03') + || (c == '\u0B3C') + || (c >= '\u0B3E' && c <= '\u0B43') || (c >= '\u0B47' && c <= '\u0B48') || (c >= '\u0B4B' && c <= '\u0B4D') + || (c >= '\u0B56' && c <= '\u0B57') || (c >= '\u0B82' && c <= '\u0B83') || (c >= '\u0BBE' && c <= '\u0BC2') + || (c >= '\u0BC6' && c <= '\u0BC8') || (c >= '\u0BCA' && c <= '\u0BCD') + || (c == '\u0BD7') + || (c >= '\u0C01' && c <= '\u0C03') || (c >= '\u0C3E' && c <= '\u0C44') || (c >= '\u0C46' && c <= '\u0C48') + || (c >= '\u0C4A' && c <= '\u0C4D') || (c >= '\u0C55' && c <= '\u0C56') || (c >= '\u0C82' && c <= '\u0C83') + || (c >= '\u0CBE' && c <= '\u0CC4') || (c >= '\u0CC6' && c <= '\u0CC8') || (c >= '\u0CCA' && c <= '\u0CCD') + || (c >= '\u0CD5' && c <= '\u0CD6') || (c >= '\u0D02' && c <= '\u0D03') || (c >= '\u0D3E' && c <= '\u0D43') + || (c >= '\u0D46' && c <= '\u0D48') || (c >= '\u0D4A' && c <= '\u0D4D') + || (c == '\u0D57') + || (c == '\u0E31') + || (c >= '\u0E34' && c <= '\u0E3A') || (c >= '\u0E47' && c <= '\u0E4E') + || (c == '\u0EB1') + || (c >= '\u0EB4' && c <= '\u0EB9') || (c >= '\u0EBB' && c <= '\u0EBC') || (c >= '\u0EC8' && c <= '\u0ECD') + || (c >= '\u0F18' && c <= '\u0F19') + || (c == '\u0F35') + || (c == '\u0F37') + || (c == '\u0F39') + || (c == '\u0F3E') + || (c == '\u0F3F') + || (c >= '\u0F71' && c <= '\u0F84') || (c >= '\u0F86' && c <= '\u0F8B') || (c >= '\u0F90' && c <= '\u0F95') + || (c == '\u0F97') + || (c >= '\u0F99' && c <= '\u0FAD') || (c >= '\u0FB1' && c <= '\u0FB7') + || (c == '\u0FB9') + || (c >= '\u20D0' && c <= '\u20DC') + || (c == '\u20E1') + || (c >= '\u302A' && c <= '\u302F') + || (c == '\u3099') + || (c == '\u309A'); + }*/ + + /** Digit - XMl Specification 1.0 [88] */ + private static final boolean Digit(char c) { + return (c >= '\u0030' && c <= '\u0039') || (c >= '\u0660' && c <= '\u0669') || (c >= '\u06F0' && c <= '\u06F9') + || (c >= '\u0966' && c <= '\u096F') || (c >= '\u09E6' && c <= '\u09EF') || (c >= '\u0A66' && c <= '\u0A6F') + || (c >= '\u0AE6' && c <= '\u0AEF') || (c >= '\u0B66' && c <= '\u0B6F') || (c >= '\u0BE7' && c <= '\u0BEF') + || (c >= '\u0C66' && c <= '\u0C6F') || (c >= '\u0CE6' && c <= '\u0CEF') || (c >= '\u0D66' && c <= '\u0D6F') + || (c >= '\u0E50' && c <= '\u0E59') || (c >= '\u0ED0' && c <= '\u0ED9') || (c >= '\u0F20' && c <= '\u0F29'); + } + + /** Extender - XMl Specification 1.0 [89] */ + private static final boolean Extender(char c) { + return c == '\u00B7' || c == '\u02D0' || c == '\u02D1' || c == '\u0387' + || c == '\u0640' || c == '\u0E46' || c == '\u0EC6' || c == '\u3005' + || (c >= '\u3031' && c <= '\u3035') || (c >= '\u309D' && c <= '\u309E') || (c >= '\u30FC' && c <= '\u30FE'); + } + + /** Whitespace - XML Specification 1.0 [3] */ + private static final boolean S(char c) { + return c == '\u0020' || c == '\u0009' || c == '\r' || c == '\n'; + } +}