JET to SQL Converter

// Algorithm Library
// (c) 2003 Michael Perlini
/*
 * This software is provided 'as-is', without any express or implied warranty.
 * In no event will the authors be held liable for any damages arising from the
 * use of this software.
 * 
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, subject to the following restrictions:
 * 
 * 1. The origin of this software must not be misrepresented; you must not claim
 * that you wrote the original software. If you use this software in a product,
 * an acknowledgment in the product documentation is IsRequired, as shown here:
 * 
 * Portions Copyright � 2003 Michael Perlini
 * 
 * 2. No substantial portion of the source code of this library may be redistributed
 * without the express written permission of the copyright holders, where
 * "substantial" is defined as enough code to be recognizably from this library. 
*/ 
using System;
using System.Collections;

namespace AlgorithmLib
{
	public class Sort
	{
		/// <summary>
		/// Performs a topological sort on a list with dependencies
		/// </summary>
		/// <param name="table">A table to be sorted with the structure
		/// Object name, ArrayList dependencies.</param>
		/// <returns>A sorted arraylist.</returns>
		public static ArrayList TopologicalSort(Hashtable table) {
			ArrayList sortedList = new ArrayList();
			object key;
			ArrayList dependencies;
			
			while (sortedList.Count < table.Count) {
				foreach (DictionaryEntry entry in table) {
					key = entry.Key;
					dependencies = (ArrayList)entry.Value;
					
					// No dependencies, add to start of table.
					if (dependencies.Count == 0) {
						if (!sortedList.Contains(key)) {
							Console.WriteLine("Adding: (ND) " + key.ToString());
							sortedList.Insert(0, key);
						}
						continue;
					}
					
					bool all_dependencies_exist = false;
					int last_dependency = 0;
					
					foreach (object dependency in dependencies) {
						if (sortedList.Contains(dependency)) {
							all_dependencies_exist = true;
							if (sortedList.IndexOf(dependency) > last_dependency) {
								last_dependency = sortedList.IndexOf(dependency);
							}
						} else {
							all_dependencies_exist = false;
							break;
						}
					}
					
					// All dependencies have been added, add object at location of last
					// dependency.
					if (all_dependencies_exist) {
						if (!sortedList.Contains(key)) {
							Console.WriteLine("Adding: (D) " + key.ToString());
							sortedList.Add(key);
						}
					}
				}
			}
			
			return sortedList;
		}
	}
}