.kor language examples

Controller.ko

/*    This file is part of the Managarm operating system.
 *   Copyright (C) 2007, 2008, 2009  Alexander van der Grinten
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

using Korona;

namespace Managarm.Drivers.X86.Fdc;

class DriveState {
	private Controller controller;
	private ubyte driveNumber;
	// must only be modified by the processing thread
	private boolean motorState;
	// waits some seconds and then disables the motor
	private Tasking.Timer motorTimer;
	
	public constructor(Controller controller, ubyte number) {
		this.controller = controller;
		this.driveNumber = number;
	}
	
	public void updateMotor() {
		if(motorTimer != null && motorTimer.activated())
			motorTimer.disable();
		motorTimer = new Tasking.Timer(delegateof disableMotor());
		motorTimer.setMillis(5000);
		motorTimer.enable();
	}
	
	// called by the timer to disable the motor
	private void disableMotor() {
		controller.postCommand(new CmdKillMotor(driveNumber), 0);
	}
}

class Controller {
	public static const uint ACTION_READ = 1;
	public static const uint ACTION_WRITE = 2;
		
	// floppy disk controller port offsets
	public static const ubyte REG_DOR = 2; // digital output register
	public static const ubyte REG_DSR = 4; // data rate select register
	public static const ubyte REG_MSR = 4; // main status register
	public static const ubyte REG_CCR = 7; // configuration control register
	public static const ubyte REG_DATA = 5; // data register
	
	// digital output register constants
	public static const ubyte DOR_NORESET = 4;
	public static const ubyte DOR_DMAGATE = 8;
	public static const ubyte DOR_MOTOR0 = 16;
	public static const ubyte DOR_MOTOR1 = 32;
	public static const ubyte DOR_MOTOR2 = 64;
	public static const ubyte DOR_MOTOR3 = 128;
	
	// configuration control register constants
	public static const ubyte CCR_RATE_500K = 0;
	
	// main status register constants
	public static const ubyte MSR_RQM = 128;
	
	// status register constants
	public static const ubyte ST0_INT_CODE = 0xC0;
	public static const ubyte ST0_SEEK_END = 32;
	
	// command constants
	public static const ubyte CMD_SPECIFY = 3;
	public static const ubyte CMD_SENSE_INT = 8;
	public static const ubyte CMD_RECALIBRATE = 7;
	public static const ubyte CMD_SEEK = 15;
	public static const ubyte CMD_WRITE_SECTOR = 5;
	public static const ubyte CMD_READ_SECTOR = 6;
	
	// flags that change command behaviour
	public static const ubyte CMDFLAG_MFM = 64; // double density (default)
	
	// drives that are managed by this controller object
	private ?DriveState drives;
	
	// stores the commands that will be executed next
	private $MinimumHeap[Command] commandQueue;
	// event that is raised when a command arrives
	private Tasking.Event commandEvent;
	// proctects the command queue from concurrent access
	private Tasking.Semaphore commandLock;
	
	private uint controllerIo;
	private uint controllerIrq;
	
	// current drive that is selected
	// must only be modified by the processing thread
	private ubyte currentDrive;
	
	public constructor(uint ctrlio, uint ctrlirq) {
		this.controllerIo = ctrlio;
		this.controllerIrq = ctrlirq;
		
		// create the command queue
		commandQueue = new $MinimumHeap[Command]
				(delegateof Command.comparePriority(Command, Command));
		commandLock = new Tasking.Semaphore();
		commandEvent = new Tasking.Event();
		
		// create the drive state structures
		drives = new DriveState[4];
		drives[0] = new DriveState(this, 0);
		drives[1] = new DriveState(this, 1);
		drives[2] = new DriveState(this, 2);
		drives[3] = new DriveState(this, 3);
		
		Tasking.Thread processor = new Tasking.Thread(delegateof process());
		processor.startup();
	}
	
	public void postCommand(Command command, uint priority) {
		command.priority = priority; // set the priority value
		
		commandLock.acquire();
		commandQueue.insert(command);
		commandEvent.fire();
		commandLock.release();
	}
	
	public void process() {
		// initialize the fdc
		resetController();
		
		def Tasking.Listener listener = commandEvent.listen();
		while(true) {
			commandLock.acquire();
			listener.reset();
			Command command = commandQueue.fetch();
			commandLock.release();
			
			// if there is a command we execute it
			// otherwise we sleep until a command arrives
			if(command != null) {
				execute(command);
			}else{
				listener.waitfor();
			}
		}
	}
	
	// processes a single command
	// must only be called by the processing thread
	private void execute(Command command) {
		if(command instanceof CmdKillMotor) {
			CmdKillMotor cmdobject = cast[CmdKillMotor]command;
			shutdownMotor(cmdobject.driveNumber);
		}else if(command instanceof CmdRwSector) {
			CmdRwSector cmdobject = cast[CmdRwSector]command;
			readWriteSector(cmdobject.action, cmdobject.driveNumber,
					cmdobject.sectorNumber, cmdobject.buffer);
			
			// let the finish event fire
			cmdobject.currentState = CmdRwSector.STATE_SUCCESS;
			cmdobject.stateEvent.fire();
		}else{
			System.errOut.writeLn("Illegal command for execute()");
		}
	}
	
	// must only be called by the processing thread
	private void shutdownMotor(ubyte drivenum) {
		drives[cast[uint]drivenum].motorState = false;
		updateDrive();
	}
	
	// must only be called by the processing thread
	private void readWriteSector(uint action, ubyte drivenum,
			uint secnum, ?ubyte buffer) {
		selectDrive(drivenum);
		
		// program the data rate
		Managarm.ManaIo.writeIo8(controllerIo, REG_CCR, CCR_RATE_500K);
		
		// calculate the chs values of the sector
		ubyte chs_sector = cast[ubyte](secnum % 18 + 1);
		ubyte chs_cylinder = cast[ubyte](secnum / 18 / 2);
		ubyte chs_head = cast[ubyte](secnum / 18 % 2);
		
		// execute a recalibrate command (try it 5 times)
		uint recal_tries = 5;
		while(recal_tries != 0 && recalibrate() == false)
			recal_tries--;
		if(recal_tries == 0)
			System.stdOut.writeLn("recalibrate() failed!");
		
		// execute a seek command (try it 5 times)
		// TODO: do we have to send this command?
		uint seek_tries = 5;
		while(seek_tries != 0 && seek(chs_cylinder) == false)
			seek_tries--;
		if(seek_tries == 0)
			System.stdOut.writeLn("seek() failed!");
		
		setupDma();
		
		// send the read sectors command
		// note that we operate in double density (mfm) mode
		resetIrq();
		if(action == ACTION_READ) {
			sendCommand(CMD_READ_SECTOR | CMDFLAG_MFM);
		}else{
			sendCommand(CMD_WRITE_SECTOR | CMDFLAG_MFM);
		}
		sendCommand((chs_head << 2) | drivenum);
		sendCommand(chs_cylinder);
		sendCommand(chs_head);
		sendCommand(chs_sector);
		// sets the length of one sector to 512 bytes
		sendCommand(2);
		// number of sectors this command operates on
		sendCommand(18);
		// length of gap3. must be 27 for 3 1/2" disks
		sendCommand(27);
		// has no meaning when sector size == 512 but intel says
		// this byte should be set to 0xFF
		sendCommand(0xFF);
		waitforIrq();
		
		for(uint i = 0; i < 512; i++)
			buffer[i] = Managarm.ManaIo.readMemDirect8(0xFF803000 + i);
		
		// read the results (and ignore most bytes)
		ubyte st0 = readResult();
		readResult(); // st1 register
		readResult(); // st2 register
		readResult(); // current cylinder
		readResult(); // current head
		readResult(); // current sector
		readResult(); // sector size constant
		
		if(st0 & ST0_INT_CODE != 0)
			System.errOut.writeLn("readWriteSectors() failed!");
	}
	
	// must only be called by the processing thread
	private boolean seek(ubyte cylinder) {
		// send the seek command
		resetIrq();
		sendCommand(CMD_SEEK);
		sendCommand(currentDrive);
		sendCommand(cylinder);
		waitforIrq();
		
		// we have to send an sense interrupt status command to make
		// sure that the seek command succeded
		sendCommand(CMD_SENSE_INT);
		ubyte res_st0 = readResult();
		ubyte res_pcn = readResult();
		if(res_st0 & ST0_SEEK_END == 0 || res_pcn != cylinder)
			return false;
		return true;
		
		// wait until the head is at the correct position
		System.waitMillis(15);
	}
	
	// must only be called by the processing thread
	private void selectDrive(ubyte drivenum) {
		currentDrive = drivenum;
		
		drives[cast[uint]drivenum].updateMotor();
		
		if(drives[cast[uint]drivenum].motorState) {
			updateDrive(); // update the fdc registers
		}else{
			// we have to start the motor and wait until it is running
			drives[cast[uint]drivenum].motorState = true;
			updateDrive(); // update the fdc registers
			
			// wait until the motor is running
			// intels says the motor should be running in 300ms for 3 1/2" disks
			System.waitMillis(300);
		}
	}
	
	// enable/disable motors and select the drive
	// must only be called by the processing thread
	private void updateDrive() {
		// set the current drive flag and other basic flags
		ubyte dorflags = currentDrive | DOR_NORESET | DOR_DMAGATE;
		if(drives[0].motorState) dorflags |= DOR_MOTOR0;
		if(drives[1].motorState) dorflags |= DOR_MOTOR1;
		if(drives[2].motorState) dorflags |= DOR_MOTOR2;
		if(drives[3].motorState) dorflags |= DOR_MOTOR3;
		
		// write the dor register
		Managarm.ManaIo.writeIo8(controllerIo, REG_DOR, dorflags);
	}
	
	// must only be called by the processing thread
	private void resetController() {
		// enter reset state and leave it immediately
		resetIrq();
		Managarm.ManaIo.writeIo8(controllerIo, REG_DOR, 0);
		System.waitMicros(250); // XXX: make sure that 250 usecs are enough
		Managarm.ManaIo.writeIo8(controllerIo, REG_DOR,
				DOR_NORESET | DOR_DMAGATE);
		waitforIrq();
		
		// program the data rate
		Managarm.ManaIo.writeIo8(controllerIo, REG_CCR, CCR_RATE_500K);
		
		// send four sense interrupt commands (required by the specification)
		for(uint i = 0; i < 4; i++) {
			sendCommand(CMD_SENSE_INT);
			ubyte res_st0 = readResult();
			ubyte res_pcn = readResult();
		}
		
		// send the specify cmd
		sendCommand(CMD_SPECIFY);
		// set some magic numbers: activate non-dma mode,
		// step rate: 3ms, head unload time: 240ms, head load time: 16ms
		sendCommand(223);
		sendCommand(2);
	}
	
	// sends a recalibrate command to the fdc
	// returns true if the command was successful
	// must only be called by the processing thread
	private boolean recalibrate() {
		// send the recalibrate command
		resetIrq();
		sendCommand(CMD_RECALIBRATE);
		sendCommand(currentDrive);
		waitforIrq();
		
		// we have to send an sense interrupt status command to make
		// sure that the recalibrate command succeded
		sendCommand(CMD_SENSE_INT);
		ubyte res_st0 = readResult();
		ubyte res_pcn = readResult();
		if(res_st0 & ST0_SEEK_END == 0 || res_pcn != 0)
			return false;
		return true;
	}
	
	// sends a command byte to the floppy disk controller
	// must only be called by the processing thread
	private void sendCommand(ubyte command) {
		// wait until the fdc is ready
		while(Managarm.ManaIo.readIo8(controllerIo, REG_MSR) & MSR_RQM == 0) {
			// TODO: do something useful
		}
		
		Managarm.ManaIo.writeIo8(controllerIo, REG_DATA, command);
	}
	
	// receives a result byte from the floppy disk controller
	// must only be called by the processing thread
	private ubyte readResult() {
		// wait until the fdc is ready
		while(Managarm.ManaIo.readIo8(controllerIo, REG_MSR) & MSR_RQM == 0) {
			// TODO: do something useful
		}
		
		return Managarm.ManaIo.readIo8(controllerIo, REG_DATA);
	}
	
	private void resetIrq() {
		IntfThreads.block(IntfThreads.getCurrent(), false);
		Managarm.ManaEvents.waitfor(controllerIrq);
	}
	
	private void waitforIrq() {
		IntfThreads.sleep(IntfThreads.getCurrent(), false);
	}
	
	// FIXME: horrible hack
	private void setupDma() {
		uint address = 0x80000;
		uint dmabytes = 511; // bytes to transfer minus one
		
		// disable channel, flip-flop and mode
		Managarm.ManaIo.writeIoDirect8(0x0A, 2 | 0x4);
		Managarm.ManaIo.writeIoDirect8(0x0C, 0);
		Managarm.ManaIo.writeIoDirect8(0x0B, 0x44 | 2);
			
		// address
		Managarm.ManaIo.writeIoDirect8(0x04, cast[ubyte]address & 0xFF);
		Managarm.ManaIo.writeIoDirect8(0x04, cast[ubyte](address >> 8) & 0xFF);
		Managarm.ManaIo.writeIoDirect8(0x81, cast[ubyte](address >> 16) & 0xFF);
			
		// flip-flop
		Managarm.ManaIo.writeIoDirect8(0x0C, 0);
			
		// byte count
		Managarm.ManaIo.writeIoDirect8(0x05, cast[ubyte]dmabytes & 0xFF); 
		Managarm.ManaIo.writeIoDirect8(0x05, cast[ubyte](dmabytes >> 8) & 0xFF);
			
		// enable channel
		Managarm.ManaIo.writeIoDirect8(0x0A, 2);
	}
}

RbTreeMap.kor

/*    This file is part of the managarm operating system.
 *   Copyright (C) 2007, 2008, 2009  Alexander van der Grinten
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

// this file implements a map based on red-black trees

namespace Korona;

generic class MapIterator[KEYTYPE, OBJTYPE] extends $Iterator[$MapEntry[KEYTYPE, OBJTYPE]] {
	// next element that will be returned
	private $MapEntry[KEYTYPE, OBJTYPE] current;
	// last element that was returned
	private $MapEntry[KEYTYPE, OBJTYPE] lastElement;
	
	constructor($MapEntry[KEYTYPE, OBJTYPE] root) {
		if(root == null)
			return;
		// get the leftmost element
		$MapEntry[KEYTYPE, OBJTYPE] element = root;
		while(element.left != null)
			element = element.left;
		current = element;
	}
	
	// inherited from $Iterator
	public boolean hasNext() {
		if(current == null)
			return false;
		return true;
	}
	
	// inherited from $Iterator
	public $MapEntry[KEYTYPE, OBJTYPE] next() {
		// memorize the current element to return it later
		lastElement = current;
		
		// find the the next element in the tree
		if(current.right != null) {
			// it's in the node's right subtree
			current = current.right;
			
			while(current.left != null)
				current = current.left;
			return lastElement;
		}
		
		// it's at an upper layer of the tree
		while(current.parent != null
				&& current != current.parent.left)
			current = current.parent;
		if(current != null)
			current = current.parent;
		return lastElement;
	}
	
	public void remove() {
		lastElement.remove();
		__gc_destruct$(lastElement$);
	}
}

generic class KeyIterator[KEYTYPE, OBJTYPE] extends $Iterator[KEYTYPE] {
	// an iterator we get our objects from
	private $Iterator[$MapEntry[KEYTYPE, OBJTYPE]] iterator;
	
	public constructor($MapEntry[KEYTYPE, OBJTYPE] root) {
		iterator = new $MapIterator[KEYTYPE, OBJTYPE](root);
	}
	
	// inherited from $Iterator
	public boolean hasNext() {
		return iterator.hasNext();
	}
	
	// inherited from $Iterator
	public KEYTYPE next() {
		return iterator.next().key;
	}
	
	// inherited from $Iterator
	public void remove() {
		iterator.remove();
	}
	
$ifdef LIBKOR_MARGINAL_RUNTIME $<--
	// inherited from Korona.Object
	public void __destruct() {
		__gc_destruct$(iterator$);
	}
$-->
}

generic class ValueIterator[KEYTYPE, OBJTYPE] extends $Iterator[OBJTYPE] {
	// an iterator we get our objects from
	private $Iterator[$MapEntry[KEYTYPE, OBJTYPE]] iterator;
	
	public constructor($MapEntry[KEYTYPE, OBJTYPE] root) {
		iterator = new $MapIterator[KEYTYPE, OBJTYPE](root);
	}
	
	// inherited from $Iterator
	public boolean hasNext() {
		return iterator.hasNext();
	}
	
	// inherited from $Iterator
	public OBJTYPE next() {
		return iterator.next().object;
	}
	
	// inherited from $Iterator
	public void remove() {
		iterator.remove();
	}
	
$ifdef LIBKOR_MARGINAL_RUNTIME $<--
	// inherited from Korona.Object
	public void __destruct() {
		__gc_destruct$(iterator$);
	}
$-->
}

generic class Map[KEYTYPE, OBJTYPE] {
	private static final uint COLOR_RED = 1;
	private static final uint COLOR_BLACK = 2;
	
	// comparator used to compare different entries of this map
	private $Comparator[local KEYTYPE] comparator;
	
	// list of entries in this map
	private $MapEntry[KEYTYPE, OBJTYPE] root;
	
	private uint numberOfElements;
	
	public final constructor($Comparator[local KEYTYPE] comparator) {
		this.comparator = comparator;
	}
	
	// adds one entry to this map
	public final void add(KEYTYPE key, OBJTYPE object) {
		// create a new map entry
		$MapEntry[KEYTYPE, OBJTYPE] element
				= new $MapEntry[KEYTYPE, OBJTYPE](this, key, object);
		
		numberOfElements++;
				
		// if the tree is empty "element" becomes the root
		if(root == null) {
			root = element;
			restoreAfterInsert(element);
			return;
		}
		
		// add "element" as a leaf to the tree			
		$MapEntry[KEYTYPE, OBJTYPE] entry = root;
		while(true) {
			uint result = comparator.compare(key, entry.key);
			
			/* ---- add it the the left subtree ---- */
			if(result == Util.CMP_LESS) {
				if(entry.left == null) {
					entry.left = element;
					element.parent = entry;
					restoreAfterInsert(element);
					return;
				}else{
					entry = entry.left;
				}
			/* ---- add it to the right subtree ---- */
			}else if(result == Util.CMP_GREATER) {
				if(entry.right == null) {
					entry.right = element;
					element.parent = entry;
					restoreAfterInsert(element);
					return;
				}else{
					entry = entry.right;
				}
			}else if(result == Util.CMP_EQUAL) {
				System.errOut.put(Reflection.getClassName(this)).putln(":");
				System.errOut.formatLn("add(): Element already in map sorted by %s",
					arrayof(new String(Reflection.getClassName(comparator))));
				System.exit();
			}else{
				System.errOut.formatLn("add(): No total order for %s",
					arrayof(new String(Reflection.getClassName(comparator))));
				System.exit();
			}
		}
	}
	
	public final void restoreAfterInsert($MapEntry[KEYTYPE, OBJTYPE] node) {
		// color the node red
		node.color = COLOR_RED;
		
		// if "node" is the root of the tree, color it black
		if(node.parent == null) {
			node.color = COLOR_BLACK;
		}else if(node.parent.color == COLOR_BLACK) {
			// replacing a black "null" node by a red node
			// with black leaves doesn't violate
			// any red-black properties if the parent node is black.
			// when a leaf is replaced by a red node and the parent is
			// red property 4 is violated.
			return;
		}else{
			$MapEntry[KEYTYPE, OBJTYPE] grandparent = node.getGrandparent();
			$MapEntry[KEYTYPE, OBJTYPE] uncle = node.getUncle();
		
			if(uncle != null && uncle.color == COLOR_RED) {
				node.parent.color = COLOR_BLACK;
				uncle.color = COLOR_BLACK;
				grandparent.color = COLOR_RED;
				restoreAfterInsert(grandparent);
			}else if(node == node.parent.right
					&& node.parent == grandparent.left) {
				node.parent.rotateLeft();
				furtherRestoreAfterInsert(node.left);
			}else if(node == node.parent.left
					&& node.parent == grandparent.right) {
				node.parent.rotateRight();
				furtherRestoreAfterInsert(node.right);
			}else{
				furtherRestoreAfterInsert(node);
			}
		}
	}
	
	public final void furtherRestoreAfterInsert($MapEntry[KEYTYPE, OBJTYPE] node) {
		$MapEntry[KEYTYPE, OBJTYPE] grandparent = node.getGrandparent();
		
		node.parent.color = COLOR_BLACK;
		grandparent.color = COLOR_RED;
		
		if(node == node.parent.left && node.parent == grandparent.left) {
			grandparent.rotateRight();
		}else{
			grandparent.rotateLeft();
		}
	}
	
	public void removeEntry($MapEntry[KEYTYPE, OBJTYPE] entry) {
		if(entry.left != null && entry.right != null) {
			// replace the node with its in-order successor
			// the successor has only one child so deleting it is easy
			$MapEntry[KEYTYPE, OBJTYPE] successor = entry.right;
			while(successor.left != null)
				successor = successor.left;
			entry.swapWith(successor);
		}
		
		numberOfElements--;
		
		// we can be sure entry has at most one child now
		$MapEntry[KEYTYPE, OBJTYPE] child = null;
		if(entry.left != null)
			child = entry.left;
		if(entry.right != null)
			child = entry.right;
		
		// we will replace "entry" by "child" and thus remove child from the tree
		// entry = the element that will be deleted
		// child = the element that will remain in the tree
		
		// if the node we want to remove (entry) is red everything is fine
		if(entry.color == COLOR_RED) {
			entry.replaceBy(child);
			if(child != null)
				child.parent = entry.parent;
			return;
		}
		
		// now we can assume that "entry" is black
		// if the node that will take "entry"'s position is red
		// we color it black and we are done
		if(child != null && child.color == COLOR_RED) {
			child.color = COLOR_BLACK;
			entry.replaceBy(child);
			if(child != null)
				child.parent = entry.parent;
			return;
		}
		
		// now we can assume that both entry and child are black nodes
		
		// reverse the role of entry and child here
		// we cannot replace them yet because if we did the rebalancing code
		// won't work if "child" is null.
		// entry = the element that will remain in the tree
		// entry = the element that will be deleted
		
		fixAfterRemove(entry);
		
		// restore the original roles of "entry" and "child"
		// and finally replace "entry" by "child"
		entry.replaceBy(child);
		if(child != null) {
			child.parent = entry.parent;
			// set the color of "child" to the new color of "entry"
			child.color = entry.color;
		}
	}
	
	public void fixAfterRemove($MapEntry[KEYTYPE, OBJTYPE] node) {
		// note that "node" is always black.
		// if we are deleting the root, everything is fine
		if(node.parent == null)
			return;
		
		$MapEntry[KEYTYPE, OBJTYPE] sibling = node.getSibling();
		
		if(sibling.color == COLOR_RED) {
			node.parent.color = COLOR_RED;
			sibling.color = COLOR_BLACK;
			
			if(node == node.parent.left) {
				node.parent.rotateLeft();
			}else{
				node.parent.rotateRight();
			}
			
			// note that rotations change the sibling of "node"
			sibling = node.getSibling();
		}
		
		if(node.parent.color == COLOR_BLACK
				&& sibling.color == COLOR_BLACK
				&& (sibling.left == null || sibling.left.color == COLOR_BLACK)
				&& (sibling.right == null || sibling.right.color == COLOR_BLACK)) {
			sibling.color = COLOR_RED;
			fixAfterRemove(node.parent);
		}else if(node.parent.color == COLOR_RED
				&& sibling.color == COLOR_BLACK
				&& (sibling.left == null || sibling.left.color == COLOR_BLACK)
				&& (sibling.right == null || sibling.right.color == COLOR_BLACK)) {
			sibling.color = COLOR_RED;
			node.parent.color = COLOR_BLACK;
		}else if(node == node.parent.left
				&& sibling.color == COLOR_BLACK
				&& sibling.left != null && sibling.left.color == COLOR_RED
				&& (sibling.right == null || sibling.right.color == COLOR_BLACK)) {
			sibling.color = COLOR_RED;
			sibling.left.color = COLOR_BLACK;
			sibling.rotateRight();
			furtherFixAfterRemove(node);
		}else if(node == node.parent.right
				&& sibling.color == COLOR_BLACK
				&& (sibling.left == null || sibling.left.color == COLOR_BLACK)
				&& sibling.right != null && sibling.right.color == COLOR_RED) {
			sibling.color = COLOR_RED;
			sibling.right.color = COLOR_BLACK;
			sibling.rotateLeft();
			furtherFixAfterRemove(node);
		}else{
			furtherFixAfterRemove(node);
		}
	}
	
	public void furtherFixAfterRemove($MapEntry[KEYTYPE, OBJTYPE] node) {
		$MapEntry[KEYTYPE, OBJTYPE] sibling = node.getSibling();
		
		sibling.color = node.parent.color;
		node.parent.color = COLOR_BLACK;
		
		if(node == node.parent.left) {
			sibling.right.color = COLOR_BLACK;
			node.parent.rotateLeft();
		}else{
			sibling.left.color = COLOR_BLACK;
			node.parent.rotateRight();
		}
	}
	
	public final void assign(KEYTYPE key, OBJTYPE object) {
		$MapEntry[KEYTYPE, OBJTYPE] entry = getEntry(key);
		
		if(entry == null) {
			// add a new entry to this map
			add(key, object);
		}else{
			// change the object field of the entry
			entry.object = object;
		}
	}
	
	public final uint getSize() {
		return numberOfElements;
	}
	
	public final boolean contains(local KEYTYPE key) {
		if(getEntry(key) == null)
			return false;
		return true;
	}
	
	// returns the object associated to key
	public final OBJTYPE get(local KEYTYPE key) {
		$MapEntry[KEYTYPE, OBJTYPE] entry = getEntry(key);
		
		// if there is no such entry, return null
		if(entry == null)
			return null;
		
		// return the entry's object
		return entry.object;
	}
	
	public final $MapEntry[KEYTYPE, OBJTYPE] getEntry(local KEYTYPE key) {
		$MapEntry[KEYTYPE, OBJTYPE] entry = root;
		while(entry != null) {
			uint result = comparator.compare(key, entry.key);
			
			/* ---- look it up in the the left subtree ---- */
			if(result == Util.CMP_LESS) {
				entry = entry.left;
			/* ---- look it up in the right subtree ---- */
			}else if(result == Util.CMP_GREATER) {
				entry = entry.right;
			}else if(result == Util.CMP_EQUAL) {
				return entry;
			}else{
				System.errOut.formatLn("getEntry(): No total order for %s",
					arrayof(new String(Reflection.getClassName(comparator))));
				System.exit();
			}
		}
		
		// we could not find the element
		return null;
	}
	
	public final boolean empty() {
		if(numberOfElements > 0)
			return false;
		return true;
	}
	
	public final void remove(KEYTYPE key) {
		$MapEntry[KEYTYPE, OBJTYPE] entry = getEntry(key);
		removeEntry(entry);
		__gc_destruct$(entry$);
	}
	
	// removes a random element from the tree
	// (in this implementation the root is removed.)
	public final $MapEntry[KEYTYPE, OBJTYPE] remove() {
		$MapEntry[KEYTYPE, OBJTYPE] entry = root;
		removeEntry(entry);
		return entry;
	}
	
	public final void clear() {
		while(numberOfElements > 0) {
			$MapEntry[KEYTYPE, OBJTYPE] entry = remove();
			__gc_destruct$(entry$);
		}
	}
	
	public final $Iterator[$MapEntry[KEYTYPE, OBJTYPE]] iterator() {
		return new $MapIterator[KEYTYPE, OBJTYPE](root);
	}
	
	public final $Iterator[KEYTYPE] keyIterator() {
		return new $KeyIterator[KEYTYPE, OBJTYPE](root);
	}
	
	public final $Iterator[OBJTYPE] valueIterator() {
		return new $ValueIterator[KEYTYPE, OBJTYPE](root);
	}
}