/*
* Created by SharpDevelop.
* User: 3th
* Date: 1/1/1997
* Time: 5:48 AM
*
* To change this template use Tools |
Options | Coding | Edit Standard Headers.*/
namespace
Programming_CSharp
{
using
System;
using
System.Collections;
public class LinkedList
{
public Element head;
public Element tail;
public sealed class Element
{
public LinkedList list;
public object datum;
public Element next;
public Element( LinkedList list ,object datum , Element next)
{
this.list =list;
this.datum=datum;
this.next=next;
}
public object Datum
{get{return datum ;}}
public object Next
{get{return next;}}
}
public LinkedList ()
{
//sentinel=new Element(this,null,null);
//sentinel.next=sentinel;
//head=sentinel;
}
public Element Head
{
get{return head;}
}
public Element Tail
{
get{return tail;}
}
public bool IsEmpty
{
get{return head==null;}
}
public void Prepend(object item)
{
Element
tem=new Element(this,item,head);
if(head==null)
tail=tem;
head=tem;
}
public
void Append(object
item)
{
Element
tem=new Element(this,item,null);
if(head==null)
head=tem;
else
tail.next=tem;
tail=tem;
}
public
object First()
{
if(head==null)
throw new
Exception();
return head.datum;
}
public
object Last()
{
if(tail==null)
throw new
Exception();
return tail.datum;
}
public void Purge()
{
head=null;
tail=null;
}
public void Extract(object item)
{
Element
ptr=head;
Element
prevptr=null;
while(ptr!=null&&ptr.datum!=item)
{
prevptr=ptr;
ptr=ptr.next;
}
if(ptr==null)
throw new
ArgumentException("item not found");
if(ptr==head)
head=ptr.next;
else
prevptr.next=ptr.next;
if(ptr==tail)
tail=prevptr;
}
}
//*********************************************************
public class StackAsLinkedList
{
public
LinkedList list;
public int count;
public StackAsLinkedList()
{
list=new LinkedList();
list.Purge();
count=0;
}
public int Count
{get{ return count;}}
public void Push(object obj)
{
list.Prepend(obj);
count
++;
}
public object Pop()
{
if(count==0)
throw new
ArgumentException("stack is Empty");
object result =list.First();
list.Extract(result);
--count;
return result;
}
public object Top
{
get
{
if(count==0)
throw new
ArgumentException("stack is Empty");
return list.First();
}
}
}
//*********************************************************
public class GeneralTree
{
public object key;
public int degree;
public LinkedList list;
public GeneralTree(object
key)
{
this.key=key;
degree=0;
list
=new LinkedList();
}
public void purge()
{
list.Purge();
degree =0;
}
public object Key
{get{return key;}}
public GeneralTree GetSubTree(int i)
{
if(i<0||i>=degree)
throw new
ArgumentException("index out of range");
LinkedList
.Element ptr =list.Head;
for (int j
=0;j<i;j++)
ptr=(LinkedList.Element)ptr.Next;
return (( GeneralTree )(ptr.Datum));
}
public bool IsLeaf
{
get
{
if(this.degree==0)
return true;
return false;
}
}
}
//***********************************************************
public class record
{
public char c;
public int number;
public record(char s,int n)//key
{
c=s;
number=n;
}
}
public class PD
{
//********************************
private class PDEnumerator
: IEnumerator
{
public
PDEnumerator(PD lbt)
{
this.lbt
= lbt;
arr=new ArrayList();
stack=new StackAsLinkedList();
name="";
index = 0;
tree=new
GeneralTree(new record ('@',0));
}
public bool MoveNext( )
{
if (index==lbt.number)
return
false;
if(((arr.Count==0)||((stack.Count==1)&&(((GeneralTree)arr[arr.Count-1]).IsLeaf)))&&(w<lbt.T.degree))
{
tree=lbt.T.GetSubTree(w++);
if(stack.count==1)
stack.Pop();
int y=arr.Count;
for(int
i=0;i<y;i++)
{
arr.RemoveAt(arr.Count-1);
}
}
if(arr.Count>0)
{
if(!((GeneralTree)arr[arr.Count-1]).IsLeaf)
{
tree=(GeneralTree)arr[arr.Count-1];
while(((record)(tree.key)).number==0)
{
if(tree.degree>1)
{ stack.Push(null);
for(int
x=tree.degree-1;x>0;x--)
stack.Push(tree.GetSubTree(x));
//to
split subtree of each tree
}
arr.Add(tree);
tree=tree.GetSubTree(0);
}
arr.Add(tree);
index++;
return(index<=lbt.number);
}
while(((GeneralTree)arr[arr.Count-1]).degree<=1)
{
arr.RemoveAt(arr.Count-1);
}
if(stack.Top==null)
{
stack.Pop();
arr.RemoveAt(arr.Count-1);
while(((GeneralTree)arr[arr.Count-1]).degree<=1)
{
arr.RemoveAt(arr.Count-1);
}
}
tree=((GeneralTree)stack.Pop());
}
while(((record)(tree.key)).number==0)
{
if(tree.degree>1)
{ stack.Push(null);
for(int
x=tree.degree-1;x>0;x--)
stack.Push(tree.GetSubTree(x));
//to
split subtree of each tree
}
arr.Add(tree);
tree=tree.GetSubTree(0);
}
arr.Add(tree);
index++;
return(index<=lbt.number);
}
public void Reset( )
{
index = 0;
w=0;
}
public object Current
{
get
{
name="";
for(int i=0;i<arr.Count;i++)
{
name=name+((record)(((GeneralTree)arr[i]).key)).c;
}
return
name;
}
}
public
PD lbt;
public int w;
public int index;
public string name;
public
StackAsLinkedList stack;
public
ArrayList arr;
public
GeneralTree tree;
}
public
IEnumerator GetEnumerator( )
{
return
(IEnumerator) new PDEnumerator(this);
}
//****************************************************
public GeneralTree T;
int count =0;
public PD()
{
char emp='#';
T=new GeneralTree(new
record (emp ,0));
}
//*********************************************************
public void Insert(string name,int
number )
{
int i=0;int x=0;int a=0;
GeneralTree
tree=new GeneralTree(new
record ('@',0));
//Console.WriteLine((((record)(T.key)).c).ToString());
for(a=0;a<T.degree;a++)
{
if
(((record)(T.GetSubTree(a).key)).c==name[0])
{
tree=T.GetSubTree(a);
break;
}
}
if
((((record)(T.key)).c!=name[0])&&(a==T.degree))
{
T.degree++;
T.list.Append((new GeneralTree (new
record((char)name[0],0))));
int index=T.degree-1;
tree=T.GetSubTree(index);
//Console.WriteLine((((record)(tree.key)).c).ToString());
}
for ( x=1;x<name.Length-1;x++)
{
for(i=0;i<tree.degree;i++)
{
if
(((record)(tree.GetSubTree(i).key)).c==name[x])
{
tree=tree.GetSubTree(i);
break;
}
}
if
((((record)(tree.key)).c!=name[x])&&(i==tree.degree))
{
while(x<name.Length-1)
{
tree.degree++;
tree.list.Append((new GeneralTree (new
record((char)name[x],0))));
int index=tree.degree-1;
tree=tree.GetSubTree(index);
//Console.WriteLine((((record)(tree.key)).c).ToString());
x++;
}
break;
}
}
tree.degree++;
tree.list.Append((new GeneralTree (new
record((char)name[x],number))));
//Console.WriteLine((((record)(tree.GetSubTree(0).key)).c).ToString());
count++;
}
//**********************************************
public void Remove (string name)
{
StackAsLinkedList ss=new
StackAsLinkedList();
int i=0;int a=0;int x=0;
GeneralTree tree=new GeneralTree(new record ('@',0));
for(a=0;a<T.degree;a++)
{
if
(((record)(T.GetSubTree(a).key)).c==name[0])
{
tree=T.GetSubTree(a);Console.WriteLine((((record)(tree.key)).c).ToString());
ss.Push(tree);
break;
}
}
for (
x=1;x<name.Length;x++)
{
for(i=0;i<tree.degree;i++)
{
if
(((record)(tree.GetSubTree(i).key)).c==name[x])
{
tree=tree.GetSubTree(i);
ss.Push(tree);
break;
}
}
}
if((ss.Count==0)||(((record)(tree.key)).c)!=name[x-1])
throw new
ArgumentException("the name not found ");
if(tree.IsLeaf)
{
ss.Pop();
tree=(GeneralTree
)ss.Pop();//Console.WriteLine((((record)(tree.key)).c).ToString());
while ((tree.degree==1)&&(((record)(tree.key)).number==0))
{
((GeneralTree
)ss.Top).list.Purge();
((GeneralTree
)(ss.Top)).degree=0;
tree=((GeneralTree
)ss.Pop());
}
}
else
{((record)(tree.key)).number=0;}
count--;
}
//*********************************************************
public int this[string name]
{
get
{
int
i=0;int a=0;
GeneralTree tree=new GeneralTree(new
record('@',0));
for(a=0;a<T.degree;a++)
{
if
(((record)(T.GetSubTree(a).key)).c==name[0])
{
tree=T.GetSubTree(a);
break;
}
}
for (int x=1;x<name.Length-1;x++)
{
for(i=0;i<tree.degree;i++)
{
if
(((record)(tree.GetSubTree(i).key)).c==name[x])
{
tree=tree.GetSubTree(i);
break;
}
}
}
return
((record)(tree.GetSubTree(i).key)).number;
}
set
{
int
i=0;int x=0;int
a=0;int z=0;
GeneralTree
tree=new GeneralTree(new
record ('@',0));
//Console.WriteLine((((record)(T.key)).c).ToString());
for(a=0;a<T.degree;a++)
{
if
(((record)(T.GetSubTree(a).key)).c==name[0])
{
tree=T.GetSubTree(a);
break;
}
}
if
((((record)(T.key)).c!=name[0])&&(a==T.degree))
{
T.degree++;
T.list.Append((new GeneralTree (new record((char)name[0],0))));
int index=T.degree-1;
tree=T.GetSubTree(index);
//Console.WriteLine((((record)(tree.key)).c).ToString());
}
for ( x=1;x<name.Length-1;x++)
{
for(i=0;i<tree.degree;i++)
{
if
(((record)(tree.GetSubTree(i).key)).c==name[x])
{
tree=tree.GetSubTree(i);
break;
}
}
if
((((record)(tree.key)).c!=name[x])&&(i==tree.degree))
{
while(x<name.Length-1)
{
tree.degree++;
tree.list.Append((new GeneralTree (new
record((char)name[x],0))));
int index=tree.degree-1;
tree=tree.GetSubTree(index);
//Console.WriteLine((((record)(tree.key)).c).ToString());
x++;
}
break;
}
}
for(int y=0;y<tree.degree;y++)
{
if(((record)(tree.GetSubTree(y).key)).c==name[x])
{
((record)(tree.GetSubTree(y).key)).number=value;
z=1;
}
}
if(z!=1)
{
tree.degree++;
tree.list.Append((new GeneralTree (new record((char)name[x],value))));
//Console.WriteLine((((record)(tree.GetSubTree(0).key)).c).ToString());
count++;
}
}
}
//*************************************************
public static PD operator-(PD lhs,PD rhs)
{
PD
newpd =new PD();
foreach(string name in lhs)
{
if (!rhs.Contain(name)) //ISFound is function will need
newpd.Insert(name,lhs[name]);
}
return
newpd;
}
//*************************************************
public static PD operator^(PD lhs,PD rhs)
{
PD
newpd =new PD();
foreach(string name in rhs)
{
if (lhs.Contain(name)) //ISFound is function will need
newpd.Insert(name,lhs[name]);
}
return
newpd;
}
//************************************************
public static PD operator+(PD lhs,PD rhs)
{
PD
newpd =new PD();
foreach(string name in lhs)
{
newpd.Insert(name,lhs[name]);
}
foreach(string name in rhs)
{
if (!lhs.Contain(name))
newpd.Insert(name,lhs[name]);
}
return
newpd;
}
//*************************************************
public int number
{get{return count;}}
//**************************************************
public bool Contain(string name)
{
int i=0;int a=0;int x=0;
GeneralTree tree =new GeneralTree(new
record ('@',0));
for(a=0;a<T.degree;a++)
{
if
(((record)(T.GetSubTree(a).key)).c==name[0])
{
tree=T.GetSubTree(a);
break;
}
}
if((((record)(tree.key)).c!=name[x])&&(i==T.degree))
return false;
for (int y=0;y<name.Length;y++)
{
for(i=0;i<tree.degree;i++)
{
if
(((record)(tree.GetSubTree(i).key)).c==name[y])
{
tree=tree.GetSubTree(i);
break;
}
if((((record)(tree.key)).c!=name[y])&&(i==tree.degree))
return false;
}
}
return
true;
}
//********************************************************************************
public static bool operator==(PD lhs,PD rhs)
{
foreach(string name in lhs)
{
if(!rhs.Contain(name))
return false;
}
return true;
}
public static bool operator!=(PD
lhs,PD rhs)
{
return !(lhs == rhs);
}
public
override bool
Equals(object o)
{
if (o is
PD)
{
return
false;
}
return this==(PD) o;
}
public
override int
GetHashCode()
{
return 0;
}
//******************************************
public static PD empty()
{return new PD ();}
//******************************************
public
ArrayList allname()
{
ArrayList newarr=new ArrayList();
foreach(string name in this)
newarr.Add(name);
return newarr;
}
//*****************************************
public
ArrayList allphones()
{
ArrayList newarr=new ArrayList();
foreach(string name in this)
newarr.Add(this[name]);
return newarr;
}
public
ArrayList Names(string start)
{
ArrayList
arr=new ArrayList();
foreach(string n in this)
{
if(n.StartsWith(start))
arr.Add(n);
}
return arr;
}
}
public class test
{
public static void Main()
{
PD
p1=new PD();
p1.Insert("adhra",1111111);
p1.Insert("amied",1111111);
p1.Insert("aewqw",1111111);
p1.Insert("rweqv",1111111);
p1.Insert("rert",1111111);
//Console.WriteLine(p1["amira"]);
p1["mrmr"]=123456;
if(!p1.Contain("dsad"))
Console.WriteLine(p1["mrmr"]);
foreach(string name in p1)
Console.WriteLine(name);
ArrayList
arr=p1.Names("a");
foreach(string n in arr)
Console.WriteLine(n);
//
p1.Remove("rert");
}
}
}