/* CoreBasics.c */

#include "malloc.h"
#include "CoreBasics.h"
	
/* Basic Operations */
	
	Nat Min(a, b)
		Nat a;
		Nat b;
		{
		if (a>b) return(b);
		else return(a);
		};
		
	Nat Max(a, b)
		Nat a;
		Nat b;
		{
		if (a>b) return(a);
		else return(b);
		};
		
/* Bit Operations */
	
	Nat powersOfTwo[32]= {0x1L, 0x2L, 0x4L, 0x8L, 0x10L, 0x20L, 0x40L, 0x80L, 0x100L, 0x200L, 0x400L, 0x800L, 0x1000L, 0x2000L, 0x4000L, 0x8000L, 0x10000L, 0x20000L, 0x40000L, 0x80000L, 0x100000L, 0x200000L, 0x400000L, 0x800000L, 0x1000000L, 0x2000000L, 0x4000000L, 0x8000000L, 0x10000000L, 0x20000000L, 0x40000000L, 0x80000000L};
		
	Nat NBits(n)
		Nat n;
		{
		Nat i;
		if (n==0) return(0);
		for (i=1; i<32; i++) if (powersOfTwo[i]>=n) return(i);
		if (n<=NatLast) return(32);
		Die;
		};
		
	Bool EBFN(container, index, containerSize)
		Nat container;
		Nat index;
		Nat containerSize;
		{
		return((container>>(containerSize-index-1))&1);
		};
		
/* Memory Management */
	
	Ref MemoryAllocate(bytes)
		Nat bytes;
		{
		return((Ref)malloc(bytes));
		};
		
/* String */
	
	Bool StringEqual(first, second)
		String first;
		String second;
		{
		if (first==nil && second==nil) return(true);
		if (first==nil || second==nil) return (false);
		while (true) {
			if (*first==0 && *second==0) return (true);
			if (*first!=*second || *first==0 || *second==0) return (false);
			first+=1;
			second+=1;
			};
		};
		
	Nat StringLength(string)
		String string;
		{
		Nat length=0;
		if (string==nil) return(0);
		while (*string!=0) {
			string+=1;
			length+=1;
			};
		return(length);
		};
		
	String StringNew(size)
		Nat size;
		{
		return(MemoryAllocate(size+1));
		};
		
	void StringMove(fetch, store)
		char *fetch;
		char *store;
		{
		if (fetch==nil) return;
		while (*fetch!=0) {
			*store = *fetch;
			fetch+=1;
			store+=1;
			};
		};
		
	String StringCat(first, second)
		String first;
		String second;
		{
		Nat firstLength=StringLength(first);
		Nat secondLength=StringLength(second);
		String new=StringNew(firstLength+secondLength);
		StringMove(first, new);
		StringMove(second, new+firstLength);
		new[firstLength+secondLength]=0;
		return(new);
		};
		
	String StringFromNat(number)
		Nat number;
		{
		String string;
		char stack[32];
		Nat nChars=0;
		Nat i;
		while (true) {
			Nat digit=number%10;
			stack[nChars]=digit+'0';
			nChars+=1;
			if (number<10) break;
			number=number/10;
			};
		string=StringNew(nChars);
		for (i=0; i<nChars; i++) string[i]=stack[nChars-i-1];
		return(string);
		};
		
	void StringPrintIndent(indent, cr)
		Nat indent;
		Bool cr;
		{
		Nat i;
		if (cr) {
			printf("\n");
			for (i=0; i<indent; i++) printf("  ");
			}
		else printf(", ");
		};
		
/* List */
	
	List ListCons(list, item)
		List list;
		Ref item;
		{
		List new=New(List, ListRec);
		new->first=item;
		new->rest=list;
		return(new);
		};
		
	Nat ListLength(list)
		List list;
		{
		Nat length=0;
		while (list!=nil) {
			length+=1;
			list=list->rest;
			};
		return(length);
		};
		
	Bool ListEnumerate(list, each, context)
		List list;
		ListItemProc each;
		Ref context;
		{
		Bool quit=false;
		while (list!=nil) {
			if (quit=each(list->first, context)) break;
			list=list->rest;
			};
		return(quit);
		};
		
	Bool ListMemberString(list, candidate)
		ListOfString list;
		String candidate;
		{
		while (list!=nil) {
			if (StringEqual(list->first, candidate)) return(true);
			list=list->rest;
			};
		return(false);
		};
		
/* Property */
	
	Property PropertyCreate(rest, key, value)
		Property rest;
		Atom key;
		Ref value;
		{
		Property property;
		property=New(Property, PropertyRec);
		property->rest=rest;
		property->key=key;
		property->value=value;
		return(property);
		};
		
	Nat uniqueID=0;
	String *propertyNames;
	PropertyPrintProc *propertyPrintProcs;
		
	Atom PropertyRegister(name, printProc) 
		String name;
		PropertyPrintProc printProc;
		{
		PropertyPrintProc *newPrintProcs;
		String *newPropNames;
		Nat i;
		newPropNames=(String *)malloc((uniqueID+1)*sizeof(String));
		newPrintProcs=(PropertyPrintProc *)malloc((uniqueID+1)*sizeof(PropertyPrintProc));
		for (i=0; i<uniqueID; i++) {
			newPropNames[i]=propertyNames[i];
			newPrintProcs[i]=propertyPrintProcs[i];
			};
		newPropNames[uniqueID]=name;
		newPrintProcs[uniqueID]=printProc;
		propertyNames=newPropNames;
		propertyPrintProcs=newPrintProcs;
		uniqueID+=1;
		return((Atom)uniqueID-1);
		};
		
	Ref PropertyGet(from, property)
		Properties from;
		Atom property;
		{
		while (from) {
			if (from->key==property) return(from->value);
			from=from->rest;
			};
		return(nil);
		};
		
	Properties PropertyPut(on, property, value)
		Properties on;
		Atom property;
		Ref value;
		{
		Properties scan=on;
		Properties trail=nil;
		while (scan) {
			if (scan->key==property) {
				if (value==nil) {
					if (trail==nil) return(on->rest);
					trail->rest=scan->rest;
					return(on);
					};
				scan->value=value;
				return(on);
				};
			trail=scan;
			scan=scan->rest;
			};
		if (value!=nil) return(PropertyCreate(on, property, value));
		else return(on);
		};
		
	void PropertyPrint(properties, indent, cr, level)
		Properties properties;
		Nat indent;
		Bool cr;
		Nat level;
		{
		Properties scan=properties;
		while (scan) {
			Nat index=(Nat)scan->key;
			if (propertyPrintProcs[index]!=nil) (propertyPrintProcs[index])(scan->key, scan->value, indent, level, cr);
			scan=scan->rest;
			};
		};
		
	void PropertyPrintString(property, value, indent, level, cr)
		Atom property;
		Ref value;
		Nat indent;
		Nat level;
		Bool cr;
		{
		level=level;
		StringPrintIndent(indent, cr);
		printf("%s: %s", propertyNames[(Nat)property], value);
		};
		
/* Hash Table */
	
	Nat HashTableHashString(key)
		Ref key;
		{
		String string=(String)key;
		Nat hash=0;
		if (string==nil) return(0);
		while (true) {
			if (*string==0) break;
			hash=hash^(*string);
			string+=1;
			if (*string==0) break;
			hash=hash^((*string)<<8);
			string+=1;
			};
		return(hash);
		};
		
	Buckets HashTableBucketsCreate(size)
		Nat size;
		{
		Buckets buckets=NewSeq(Buckets, BucketsRec, Properties, size);
		Nat i;
		buckets->size=size;
		for (i=0; i<size; i++) buckets->elements[i]=nil;
		return(buckets);
		};
		
	HashTable HashTableCreate(size, hash, equal)
		Nat size;
		HashProc hash;
		EqualProc equal;
		{
		HashTable table=New(HashTable, HashTableRec);
		table->hash=hash;
		table->equal=equal;
		table->size=0;
		table->sizeLimit=size;
		table->buckets=HashTableBucketsCreate(size);
		return(table);
		};
		
	Nat HashTableSize(table)
		HashTable table;
		{
		return(table->size);
		};
		
	Nat ComputeIndex (table, key)
		HashTable table;
		Ref key;
		{
		Nat hash;
		if (table->hash==nil) hash=((Nat)key>>16)^(Nat)key;
		else hash=table->hash(key);
		return(hash%table->buckets->size);
		};
		
	Ref HashTableScan(table, bucket, key)
		HashTable table;
		Properties bucket;
		Ref key;
		{
		while (bucket) {
			if ((table->equal==nil && bucket->key==key) || (table->equal!=nil && table->equal(bucket->key, key))) return(bucket->value);
			bucket=bucket->rest;
			};
		return(nil);
		};
		
	Ref HashTableGet(table, key)
		HashTable table;
		Ref key;
		{
		Nat index=ComputeIndex(table, key);
		Properties bucket=table->buckets->elements[index];
		return(HashTableScan(table, bucket, key));
		};
		
#define PrimeTableSize 14
#define highPrime 32749
Nat primeTable[PrimeTableSize] = {2, 5, 11, 23, 53, 113, 251, 509, 1019, 2039, 4079, 8179, 16369, highPrime};
	
	void HashTablePut(table, key, value)
		HashTable table;
		Ref key;
		Ref value;
		{
		Nat index=ComputeIndex(table, key);
		Properties *bucket = &(table->buckets->elements[index]);
		Bool found=HashTableScan(table, *bucket, key)!=nil;
		*bucket=PropertyPut(*bucket, (Atom)key, value);
		if (found && value==nil) table->size-=1;
		else if (!found && value!=nil) {
			table->size+=1;
			if (table->size > table->sizeLimit) {
				Buckets oldBuckets=table->buckets;
				Buckets newBuckets;
				Nat seek=2*table->buckets->size;
				Nat newPTI=0;
				Nat newMod=highPrime;
				Nat i;
				if (seek >= highPrime) newPTI=PrimeTableSize-1;
				else while (true) {
					newMod=primeTable[newPTI];
					if (newMod >= seek) break;
					newPTI+=1;
					};
				if (newMod=table->buckets->size) {table->sizeLimit=0xFFFFFFFFL; return;};
				table->sizeLimit=newMod;
				newBuckets=HashTableBucketsCreate(newMod);
				table->buckets=newBuckets;
				for (i=0; i<oldBuckets->size; i++) {
					Property cur=oldBuckets->elements[i];
					Property next=nil;
					while (cur!=nil) {
						Nat newIndex=ComputeIndex(table, cur->key);
						next=cur->rest;
						cur->rest=newBuckets->elements[newIndex];
						newBuckets->elements[newIndex]=cur;
						cur=next;
						};
					if (next!=nil) Die;
					};
				};
			};
		};
			
	void HashTableFree(table)
		HashTable table;
		{
		};
		
	void HashTableUpdate(table, action, context)
		HashTable table;
		HashTableUpdateAction action;
		Ref context;
		{
		Nat i;
		for (i=0; i<table->buckets->size; i++) {
			Properties scan=table->buckets->elements[i];
			Properties trail=nil;
			while (scan) {
				scan->value=action(scan->key, scan->value, context);
				if (scan->value==nil) {
					if (trail==nil) table->buckets->elements[i]=scan->rest;
					else trail->rest=scan->rest;
					}
				else trail=scan;
				scan=scan->rest;
				};
			};
		};