1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
module Editor {
export class List<T> {
public next: List<T>;
public prev: List<T>;
private listFactory: ListFactory<T>;
constructor(public isHead: boolean, public data: T) {
this.listFactory = new ListFactory<T>();
}
public add(data: T): List<T> {
var entry = this.listFactory.MakeEntry(data);
this.prev.next = entry;
entry.next = this;
entry.prev = this.prev;
this.prev = entry;
return entry;
}
public count(): number {
var entry: List<T>;
var i: number;
entry = this.next;
for (i = 0; !(entry.isHead); i++) {
entry = entry.next;
}
return (i);
}
public isEmpty(): boolean {
return (this.next == this);
}
public first(): T {
if (this.isEmpty())
{
return this.next.data;
}
else {
return null;
}
}
public pushEntry(entry: List<T>): void {
entry.isHead = false;
entry.next = this.next;
entry.prev = this;
this.next = entry;
entry.next.prev = entry; // entry.next.prev does not show intellisense, but entry.prev.prev does
}
public push(data: T): void {
var entry = this.listFactory.MakeEntry(data);
entry.data = data;
entry.isHead = false;
entry.next = this.next;
entry.prev = this;
this.next = entry;
entry.next.prev = entry; // entry.next.prev does not show intellisense, but entry.prev.prev does
}
public popEntry(head: List<T>): List<T> {
if (this.next.isHead) {
return null;
}
else {
return this.listFactory.RemoveEntry(this.next);
}
}
public insertEntry(entry: List<T>): List<T> {
entry.isHead = false;
this.prev.next = entry;
entry.next = this;
entry.prev = this.prev;
this.prev = entry;
return entry;
}
public insertAfter(data: T): List<T> {
var entry: List<T> = this.listFactory.MakeEntry(data);
entry.next = this.next;
entry.prev = this;
this.next = entry;
entry.next.prev = entry;// entry.next.prev does not show intellisense, but entry.prev.prev does
return entry;
}
public insertEntryBefore(entry: List<T>): List<T> {
this.prev.next = entry;
entry.next = this;
entry.prev = this.prev;
this.prev = entry;
return entry;
}
public insertBefore(data: T): List<T> {
var entry = this.listFactory.MakeEntry(data);
return this.insertEntryBefore(entry);
}
}
export class ListFactory<T> {
public MakeHead<T>(): List<T> {
var entry: List<T> = new List<T>(true, null);
entry.prev = entry;
entry.next = entry;
return entry;
}
public MakeEntry<T>(data: T): List<T> {
var entry: List<T> = new List<T>(false, data);
entry.prev = entry;
entry.next = entry;
return entry;
}
public RemoveEntry<T>(entry: List<T>): List<T> {
if (entry == null) {
return null;
}
else if (entry.isHead) {
// Can't remove the head of a list!
return null;
}
else {
entry.next.prev = entry.prev;
entry.prev.next = entry.next;
return entry;
}
}
}
}
|
