deterministic queue generator.ash

int[int] symbol_sequence;
string[int] word;
string[int] buffer_word;
file_to_map("initial conditions.txt", symbol_sequence);
int[int] buffer_sequence;
int[int] buffer_buffer_sequence;
int[int][int] orbit;
int n;
int k;
int p;
int q;

int nonzero;
int hash;
int buffer_hash;
boolean[int] in_queue;
int m;
int out_of_queue_count;
int position_offset;
boolean need_to_carry;
boolean needs_tail;

//returns int to be modded in the successor generating function.
int tail_hash(int[int] input, int n, int k){
	//print_html("generating a hash");
	hash = 0;
	nonzero = 0;
	foreach i in input{
		if(i > k && nonzero <= n**k && input[i] != 0){
			hash += input[i]*i;
			nonzero++;
		}
	}
	if(hash == 0){
		hash += k+1;
	}
	return hash;
}

int[int] successor( int[int] input, int n, int k, int p, int q){
	//print_html("generating a successor");

	//throw a digit on the end of the sequence for later use.
	input[input.count() + 1] = 0;

	//count the number of distinct things in corresponding queue
	m=0;
	for i from 0 to (n-1){
		in_queue[i] = false;
		for j from 1 to k{
			if(input[j] == i){
				in_queue[i] = true;
				m++;
				break;
			}
		}
	}

	//fill the buffer sequence with the base-n digits of the output of the successor function.
	foreach i in input{
		if(i==input.count()){
			break;
		}
		//translate queue. corresponds to the n-fold baker's map.
		if(i < k){
			buffer_sequence[i] = input[i+1];
		}
		//use a tail-based hash to spit out a deterministic value.
		//the distribution of the values 0 through n-1 should
		//be identical to selection with rejection from n symbols
		//with rejection rate p/q and queue length k.
		if(i == k){
			buffer_hash = tail_hash(input,n,k);
			if(((q*buffer_hash)%(q*n-m*p)) < n*(q-p)){
				//int division returns the floor of the result, which is desired.
				buffer_sequence[k] = ((q*buffer_hash)%(q*n-m*p)) / (q-p);
			}
			else{
				//less floaty version of (buffer_hash % (n-m*p/q) -n*(1-p/q))/ (p/q)
				buffer_sequence[k] = (((q*buffer_hash) % (q*n-m*p)) - n*(q-p))/ p;
				//what we actually want is the that value-th smallest
				//number outside of the queue.
				out_of_queue_count = 0;
				for j from 0 to (n-1){
					if(!(in_queue[j])){
						if(out_of_queue_count == buffer_sequence[k]){
							buffer_sequence[k] = j;
							break;
						}
						out_of_queue_count++;
					}
				}
			}
		}

		//handle case  i==k+1 outside of loop (below) for computation time purposes.

		//multiplying the tail by (n-1)/n.
		//equivalent to subtracting tail shifted
		//right by 1 from the orignal tail
		//before shifting the result to the right by 1.
		if(i > k+1){
			//above process without accounting for "borrowing".
			buffer_sequence[i] = input[i] - input[i-1];
		}
	}
	//handle case i==k+1
	buffer_sequence[k+1] = input[k+1];
	//handle negative digits
	buffer_buffer_sequence = buffer_sequence;
	foreach i in buffer_sequence{

			//debugging
			/*
			buffer_word[i] = "";
			if(i >= k+1){
				foreach j in buffer_buffer_sequence{
					if(j==k+1){
						buffer_word[i] += "|";
					}
					if(buffer_word[i].length() != 0 && j != k+1){
						buffer_word[i]+= ","+buffer_buffer_sequence[j];
					}
					else{
						buffer_word[i]+= buffer_buffer_sequence[j];
					}
				}
				print_html(i+": "+buffer_word[i]);
			}
			*/

		while(i > k+1 && buffer_buffer_sequence[i] <= -1){
			buffer_buffer_sequence[i] += n;
			need_to_carry = true;
			position_offset = 1;
			while(need_to_carry){
				if(buffer_buffer_sequence[i-position_offset] > 0){
					buffer_buffer_sequence[i-position_offset] -= 1;
					need_to_carry = false;
				}
				else{
					buffer_buffer_sequence[i-position_offset] = n-1;
					position_offset++;
				}
			}
		}

			//debugging
			/*
			buffer_word[i] = "";
			if(i >= k+1){
				foreach j in buffer_buffer_sequence{
					if(j==k+1){
						buffer_word[i] += "|";
					}
					if(buffer_word[i].length() != 0 && j != k+1){
						buffer_word[i]+= ","+buffer_buffer_sequence[j];
					}
					else{
						buffer_word[i]+= buffer_buffer_sequence[j];
					}
				}
				print_html(i+": "+buffer_word[i]);
			}
			*/

	}

	foreach i in buffer_buffer_sequence{
		if(buffer_buffer_sequence[i] >= n){
			need_to_carry = true;
		}
	}

	while(need_to_carry){
		foreach i in buffer_sequence{
			while(i > k+1 && buffer_buffer_sequence[i] >=n){
				buffer_buffer_sequence[i-1]++;
				buffer_buffer_sequence[i] -= n;
			}

		}
		need_to_carry = false;
		foreach i in buffer_buffer_sequence{
			if(buffer_buffer_sequence[i] >= n){
				need_to_carry = true;
			}
		}
	}
	return buffer_buffer_sequence;
}

string make_word(int[int] state, int time, int k){
	//print_html("generating a word");
	foreach i in state{
		if(i==k+1){
			word[time] += "|";
		}
		if(word[time].length() != 0 && i != k+1){
			word[time]+= ","+state[i];
		}
		else{
			word[time]+= state[i];
		}
	}
	return word[time];
}

int[int][int] generate_orbit( int[int] initial, int iterations, int n, int k, int p, int q){
	needs_tail = true;
	foreach i in initial{
		if(i > k && initial[i] != 0){
			needs_tail = false;
		}
	}
	if(needs_tail){
		initial[k+1] = 1;
	}
	buffer_sequence = initial;
	orbit[0] = initial;
	for i from 1 to iterations{
		orbit[i] = successor(orbit[i-1],n,k,p,q);
		word[i] = make_word(orbit[i],i,k);
	}
	return orbit;
}

/*
for n from 3 to 5{
	for k from 3 to 6{
		for p from 1 to 9{
			clear(orbit);
			clear(word);
			clear(buffer_sequence);
			clear(buffer_buffer_sequence);
			file_to_map("initial conditions.txt", symbol_sequence);
			orbit = generate_orbit(symbol_sequence, 30, n, k, p, 10);
			print_html("generating a text file for n="+n+", k="+k+", p="+p+", q="+10);
			map_to_file(word, "orbit for n="+n+", k="+k+", p="+p+", q="+10+".txt");
			foreach i in orbit{
				print(word[i]);
			}
		}
	}
}
*/

n=5;
k=4;
q=20;


for i from 18 to 18{
	clear(orbit);
	clear(word);
	clear(buffer_sequence);
	clear(buffer_buffer_sequence);
	file_to_map("initial conditions.txt", symbol_sequence);
	orbit = generate_orbit(symbol_sequence, 1000, n, k, i, q);
	foreach i in orbit{
		print(i+": "+word[i]);
	}
	print_html("generating a text file for n="+n+", k="+k+", p="+i+", q="+q);
	map_to_file(word, "orbit for n="+n+", k="+k+", p="+i+", q="+q+".txt");
}