From Developer Community

A sample code using an ArrayList to make an OrderedList. An OrderedList is useful to avoid clone of the same object (builded from a database), to keep fast searching.

It uses binary search (dichotomie in french).

Here, it uses int for primary key but you can easily modifiy it to use string of what else.

Ask me for help.

Lists.cs

// Lists.cs

// Playing with lists !
// Copyright 2005, Yoan BLANC <yoan @ dosimple.ch>, HE-ARC (he-arc.ch)
//
// distibuted under the GPLv2 : http://opensource.org/licenses/gpl-license.php

using System;
using System.Collections;

public class Lists
{
	public static void Main(string[] argv)
	{
		Console.WriteLine("Playing with lists\n------------------\n");
		
		// Builds the atoms
		
		Atom a = new Atom(0,"A");
		Atom b = new Atom(1,"B");
		Atom c = new Atom(2,"C");
		Atom d = new Atom(3,"D");
		Atom e = new Atom(4,"E");
		Atom f = new Atom(5,"F");
		Atom g = new Atom(6,"G");
		Atom h = new Atom(7,"H");
		Atom i = new Atom(8,"I");
		Atom j = new Atom(9,"J");
		// a bad copy of j.
		Atom y = new Atom(9,"Y");
		
		// Acts !
		
		_atoms = new OrderedList();
		
		_atoms += i;
		_atoms += j;
		
		// Only use the id value ! not the reference.
		Console.WriteLine("Atoms contains j ? {0}", _atoms.Contains(y));
		
		// Clear the fields
		_atoms.Clear();
		
		Console.WriteLine("Atoms contains j ? {0}", _atoms.Contains(j));
		
		// _atoms.Add(b);
		_atoms += b;
		_atoms += g;
		_atoms += a;
		_atoms += j;
		_atoms += h;
		_atoms += d;
		_atoms += f;
		_atoms += e;
		_atoms += c;
		_atoms += i;
		
		Console.WriteLine("Atoms contains a ? {0}", _atoms.Contains(a));
		
		_atoms -= b;
		_atoms -= a;
		
		Console.WriteLine("Atoms contains a ? {0}", _atoms.Contains(a));
		
		show();
	}
	
	// Show the string representation
	public static void show()
	{
		Console.WriteLine("\n" + TooString());
	}
	
	// Gets a string representation of the list
	public static string TooString()
	{
		string val = "";
		foreach(object atom in _atoms)
		{
			val += String.Format("{1}", ((Atom)atom).Id, ((Atom)atom).Name);
		}
		return val;
	}
	
	private static OrderedList _atoms;
}

public class OrderedList : IEnumerable
{
	public IOrderable this[int id]
	{
		get
		{
			return (IOrderable)_list[IndexOf(id)];
		}
	}
	
	public int Count
	{
		get
		{
			return _list.Count;
		}
	}
	
	public static OrderedList operator+	(OrderedList list, IOrderable value)
	{
		list.Add(value);
		return list;
	}
	
	public static OrderedList operator- (OrderedList list, IOrderable value)
	{
		list.Remove(value);
		return list;
	}
	
	// ------------------------------------------------------------------------
	
	public OrderedList()
	{
		_list = new ArrayList();
	}

	// ------------------------------------------------------------------------
	
	// 
	public int Add(IOrderable value)
	{
		int start = 0;
		int end = _list.Count - 1;
		int pivot = end;
		int pos = 0;
		
		while(start <= end)
		{
			pivot = (end + start) / 2;
			
			int cmp = ((IOrderable)_list[pivot]).CompareTo(value);
			
			if(start >= end)
			{
				if(cmp > 0)
					pos = pivot;
				else
					pos = pivot + 1;
				break;
			}
			else if (cmp > 0)
			{
				end = pivot;
			}
			else
			{
				start = pivot + 1;
			}
		}
		
		_list.Insert(pos, value);
		return pos;
	}
	
	// remove the given object
	public void Remove(IOrderable value)
	{
		Remove(value.Id);
	}
	
	// remove the given id
	public void Remove(int id)
	{
		int pos = IndexOf(id);
		
		if(pos >= 0)
		{
			_list.RemoveAt(pos);
		}
	}
	
	// -1 if not found.
	public int IndexOf(int value)
	{
		int start = 0;
		int end = _list.Count - 1;
		int pivot = end;
		int pos = -1;
		
		while(start <= end)
		{
			pivot = (end + start) / 2;
			
			int cmp = ((IOrderable)_list[pivot]).CompareTo(value);
			
			if(cmp == 0)
			{
				pos = pivot;
				break;
			}
			else if (cmp > 0)
			{
				end = pivot - 1;
			}
			else
			{
				start = pivot + 1;
			}
		}
		
		return pos;
	}
	
	public void Clear()
	{
		_list.Clear();
	}
	
	public bool Contains(IOrderable value)
	{
		return(IndexOf(value.Id) >= 0);
	}
	
	public IEnumerator GetEnumerator()
	{
		return _list.GetEnumerator();
	}
	
	// ------------------------------------------------------------------------
	
	private ArrayList _list;
}

// ----------------------------------------------------------------------------

public interface IOrderable : IComparable
{
	int Id { get; }
}

// ----------------------------------------------------------------------------

// An atom, a simple object
public struct Atom : IOrderable
{
	public int Id
	{
		get
		{
			return _id;
		}
	}
	
	public string Name
	{
		get
		{
			return _name;
		}
	}
	
	// ------------------------------------------------------------------------
	
	public Atom(int id, string name)
	{
		_id = id;
		_name = name;
	}
	
	// ------------------------------------------------------------------------
	
	public int CompareTo(object b)
	{
		if(b is IOrderable)
		{
			return _id.CompareTo(((IOrderable)b).Id);
		}
		else if(b is int)
		{
			return _id.CompareTo((int)b);
		}
		else
		{
			throw new ArgumentException("Atom can only be compared with IOrderable objects.");
		}
	}
	
	// ------------------------------------------------------------------------
	
	// The name
	private string _name;
	// Id
	private int _id;
}

--Yoan Blanc

• Article
• Discussion
• Edit
• History

Personal tools