algorithms.cs

Data Structures and Algorithms with Object-Oriented Design Patterns in C# 这本书的范例代码dll自己反编译的source

        {
            int num1 = g.NumberOfVertices;
            Graph graph1 = new GraphAsLists(num1);
            for (int num2 = 0; num2 < num1; num2++)
            {
                graph1.AddVertex(num2);
            }
            PriorityQueue queue1 = new BinaryHeap(g.NumberOfEdges);
            foreach (Edge edge1 in g.Edges)
            {
                int num3 = (int) edge1.Weight;
                queue1.Enqueue(new Association(num3, edge1));
            }
            Partition partition1 = new PartitionAsForest(num1);
            while (!queue1.IsEmpty && (partition1.Count > 1))
            {
                Association association1 = (Association) queue1.DequeueMin();
                Edge edge2 = (Edge) association1.Value;
                int num4 = edge2.V0.Number;
                int num5 = edge2.V1.Number;
                Set set1 = partition1.Find(num4);
                Set set2 = partition1.Find(num5);
                if (set1 != set2)
                {
                    partition1.Join(set1, set2);
                    graph1.AddEdge(num4, num5);
                }
            }
            return graph1;
        }

        public static Graph PrimsAlgorithm(Graph g, int s)
        {
            int num1 = g.NumberOfVertices;
            Opus6.Algorithms.Entry[] entryArray1 = new Opus6.Algorithms.Entry[num1];
            for (int num2 = 0; num2 < num1; num2++)
            {
                entryArray1[num2] = new Opus6.Algorithms.Entry(false, 0x7fffffff, 0x7fffffff);
            }
            entryArray1[s].distance = 0;
            PriorityQueue queue1 = new BinaryHeap(g.NumberOfEdges);
            queue1.Enqueue(new Association(0, g.GetVertex(s)));
            while (!queue1.IsEmpty)
            {
                Association association1 = (Association) queue1.DequeueMin();
                Vertex vertex1 = (Vertex) association1.Value;
                if (!entryArray1[vertex1.Number].known)
                {
                    entryArray1[vertex1.Number].known = true;
                    foreach (Edge edge1 in vertex1.EmanatingEdges)
                    {
                        Vertex vertex2 = edge1.MateOf(vertex1);
                        int num3 = (int) edge1.Weight;
                        if (!entryArray1[vertex2.Number].known && (entryArray1[vertex2.Number].distance > num3))
                        {
                            entryArray1[vertex2.Number].distance = num3;
                            entryArray1[vertex2.Number].predecessor = vertex1.Number;
                            queue1.Enqueue(new Association(num3, vertex2));
                        }
                    }
                }
            }
            Graph graph1 = new GraphAsLists(num1);
            for (int num4 = 0; num4 < num1; num4++)
            {
                graph1.AddVertex(num4);
            }
            for (int num5 = 0; num5 < num1; num5++)
            {
                if (num5 != s)
                {
                    graph1.AddEdge(num5, entryArray1[num5].predecessor);
                }
            }
            return graph1;
        }

        public static void Translate(TextReader dictionary, TextReader inputText, TextWriter outputText)
        {
            string text1;
            SearchTree tree1 = new AVLTree();
            while ((text1 = dictionary.ReadLine()) != null)
            {
                string[] textArray1 = text1.Split(null);
                if (textArray1.Length != 2)
                {
                    throw new InvalidOperationException();
                }
                tree1.Insert(new Association(textArray1[0], textArray1[1]));
            }
            while ((text1 = inputText.ReadLine()) != null)
            {
                foreach (string text2 in text1.Split(null))
                {
                    ComparableObject obj1 = tree1.Find(new Association(text2));
                    if (obj1 == null)
                    {
                        outputText.Write("?{0}? ", text2);
                    }
                    else
                    {
                        Association association1 = (Association) obj1;
                        outputText.Write("{0} ", association1.Value);
                    }
                }
                outputText.WriteLine();
            }
        }

        public static void WordCounter(TextReader reader, TextWriter writer)
        {
            string text1;
            HashTable table1 = new ChainedHashTable(0x407);
            while ((text1 = reader.ReadLine()) != null)
            {
                foreach (string text2 in text1.Split(null))
                {
                    Association association1 = (Association) table1.Find(new Association(text2));
                    if (association1 == null)
                    {
                        table1.Insert(new Association(text2, new Counter(1)));
                    }
                    else
                    {
                        Counter counter1 = (Counter) association1.Value;
                        counter1 ++;
                    }
                }
            }
            writer.WriteLine(table1);
        }



        private class Counter : ComparableInt32
        {
            internal Counter(int value) : base(value)
            {
            }

            public static Algorithms.Counter operator ++(Algorithms.Counter counter)
            {
                counter.obj = ((int) counter.obj) + 1;
                return counter;
            }

        }

        private class EarliestTimeVisitor : AbstractVisitor
        {
            internal EarliestTimeVisitor(int[] earliestTime)
            {
                this.earliestTime = earliestTime;
            }

            public override void Visit(object obj)
            {
                Vertex vertex1 = (Vertex) obj;
                int num1 = this.earliestTime[0];
                foreach (Edge edge1 in vertex1.IncidentEdges)
                {
                    num1 = Math.Max(num1, this.earliestTime[edge1.V0.Number] + ((int) edge1.Weight));
                }
                this.earliestTime[vertex1.Number] = num1;
            }


            private int[] earliestTime;
        }

        [StructLayout(LayoutKind.Sequential)]
        private struct Entry
        {
            public bool known;
            public int distance;
            public int predecessor;
            public Entry(bool known, int distance, int predecessor)
            {
                this.known = known;
                this.distance = distance;
                this.predecessor = predecessor;
            }

        }

        private class LatestTimeVisitor : AbstractVisitor
        {
            internal LatestTimeVisitor(int[] latestTime)
            {
                this.latestTime = latestTime;
            }

            public override void Visit(object obj)
            {
                Vertex vertex1 = (Vertex) obj;
                int num1 = this.latestTime[this.latestTime.Length - 1];
                foreach (Edge edge1 in vertex1.EmanatingEdges)
                {
                    num1 = Math.Min(num1, this.latestTime[edge1.V1.Number] - ((int) edge1.Weight));
                }
                this.latestTime[vertex1.Number] = num1;
            }


            private int[] latestTime;
        }
    }
}