lookuptable.cs

c#精彩编程百例（源代码）

//  LookupTable.cs 
//  Copyright (c) 2000 Mike Krueger
//
//  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 2 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, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

using System;
using System.Collections;
using System.Drawing;

namespace SharpDevelop.Internal.Text {

	/// <summary>
	/// This class implements a keyword map. It implements a digital search trees (tries) to find
	/// a word.
	/// </summary>
	public class LookupTable
	{
		Node root = new Node(null, null);
		bool casesensitive;
		
		/// <summary>
		/// Get the object, which was inserted under the keyword <line, at offset, with length length>,
		/// returns null, if no such keyword was inserted.
		/// </summary>
		public object this[string line, int offset, int length] {
			get {
				if(length == 0)
					return null;
				
				Node next = root;
				if (casesensitive) { 
					for (int i = 0; i < length; ++i) {
						int index = ((int)line[offset + i]) % 256;
						next = next.leaf[index];
						if (next == null)
							return null;
						if (next.color != null && SharpDevelop.Tool.Text.TextUtility.RegionMatches(line, offset, length, next.word))
							return next.color;
					}
				} else {
					for (int i = 0; i < length; ++i) {
						int index = ((int)Char.ToUpper(line[offset + i])) % 256;
						next = next.leaf[index];
						if (next == null)
							return null;
						if (next.color != null && SharpDevelop.Tool.Text.TextUtility.RegionMatches(casesensitive, line, offset, length, next.word))
							return next.color;
					}
				}
				return null;
			}
		}
		
		/// <summary>
		/// Inserts an object in the tree, under keyword
		/// </summary>
		public object this[string keyword] {
			set {
				Node node = root;
				Node next = root;
				if (!casesensitive)
					keyword = keyword.ToUpper();
				
				// insert word into the tree
				for (int i = 0; i < keyword.Length; ++i) {
					int index = ((int)keyword[i]) % 256; // index of curchar
					next = next.leaf[index];             // get node to this index
					
					if (next == null) { // no node created -> insert word here
						node.leaf[index] = new Node(value, keyword);
						break;
					}
					
					if (next.word != null && next.word.Length != i) { // node there, take node content and insert them again
						string tmpword  = next.word;                  // this word will be inserted 1 level deeper (better, don't need too much 
						object tmpcolor = next.color;                 // string comparisons for finding.)
						next.color = next.word = null;
						this[tmpword] = tmpcolor;
					}
					
					if (i == keyword.Length - 1) { // end of keyword reached, insert node there, if a node was here it was
						next.word = keyword;       // reinserted, if it has the same length (keyword EQUALS this word) it will be overwritten
						next.color = value;
						break;
					}
					
					node = next;
				}
			}
		}
		
		public LookupTable(bool casesensitive)
		{
			this.casesensitive = casesensitive;
		}
		
		class Node
		{
			public Node(object color, string word)
			{
				this.word  = word;
				this.color = color;
			}
			
			public string word;
			public object color;
			
			public Node[]   leaf = new Node[256];
		}
	}
}