-
Notifications
You must be signed in to change notification settings - Fork 0
/
BigIntLL.java
218 lines (187 loc) · 5.59 KB
/
BigIntLL.java
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
package self.math;
import java.util.*;
public class BigIntLL extends AbstractBigInt {
/*
* il primo elemento della lista è la cifra più significativa dell'intero rappresentato
*/
final private List<Integer> bigInt;
/*
* regular expression che trova le corrispondenze per caratteri non numerici
*/
final static String nonNumericRegex = "\\D";
public BigIntLL(int x) {
this(Integer.toString(x));
}
/*
* il costruttore tramite una regex controlla che la stringa rappresenti un numero e che questo sia senza segno
* successivamente inizializza la lista bigInt ai valori dei singoli caratteri della stringa, dal più al meno significativo
*/
public BigIntLL(String s) {
if (s.matches(nonNumericRegex)) throw new IllegalArgumentException();
bigInt = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
bigInt.add(
Integer.parseInt(
Character.toString(
s.charAt(i)
)));
}
}
private BigIntLL(LinkedList<Integer> ll) {
this.bigInt = ll;
}
@Override
public String value() {
Iterator<Integer> it = bigInt.iterator();
StringBuilder sb = new StringBuilder();
while (it.hasNext()) {
sb.append(it.next());
}
return sb.toString();
}
/**
* migliora le performance sfruttando il metodo della struttura dati
*/
@Override
public int length() {
return bigInt.size();
}
@Override
public BigInt factory(int x) {
return new BigIntLL(x);
}
/**
* incrementa di 1 il valore del bigInt secondo l’algoritmo carta-e-penna procedendo cioè cifra per cifra
* (dalla posizione meno significativa a quella più significativa), generando il riporto
* e utilizzandolo negli stadi successivi, (infatti il listIterator della LinkedList
* parte dall'ultimo elemento e si sposta sfruttando il metodo previous())
*/
@Override
public BigInt incr() {
LinkedList<Integer> ret = new LinkedList<>(bigInt);
ListIterator<Integer> it = ret.listIterator(ret.size());
boolean riporto = true;
while(it.hasPrevious() && riporto) {
Integer current = it.previous();
if (current != 9) {
it.set(current + 1);
riporto = false;
} else {
it.set(0);
}
}
if (riporto) {
ret.addFirst(1);
}
return new BigIntLL(ret);
}
/**
* riduce di 1 il valore del bigInt secondo l’algoritmo carta-e-penna procedendo cioè cifra per cifra
* (dalla posizione meno significativa a quella più significativa), generando il riporto
* e utilizzandolo negli stadi successivi, (infatti il listIterator della LinkedList
* parte dall'ultimo elemento e si sposta sfruttando il metodo previous())
*/
@Override
public BigInt decr() throws IllegalStateException {
if (this.equals(factory(0))) throw new IllegalStateException("this is already at minimum value possible.");
LinkedList<Integer> ret = new LinkedList<>(bigInt);
ListIterator<Integer> it = ret.listIterator(bigInt.size());
boolean riporto = true;
while(it.hasPrevious() && riporto) {
Integer current = it.previous();
if (current != 0) {
it.set(current - 1);
riporto = false;
} else {
it.set(9);
}
}
it = ret.listIterator();
while(it.hasNext() && it.next() == 0) {
it.remove(); // removing trailing zeros
}
return new BigIntLL(ret);
}
/**
* il metodo migliora l'implementazione di add (metodo default), usando ancora l'algoritmo carta e penna
* invece di incrementare tante volte quanto è il valore del secondo intero
*/
@Override
public BigInt add(BigInt a) {
LinkedList<Integer> first = bigIntToLL(this);
LinkedList<Integer> second = bigIntToLL(a);
LinkedList<Integer> ret = new LinkedList<>();
int size1 = first.size();
int size2 = second.size();
ListIterator<Integer> it1 = null;
ListIterator<Integer> it2 = null;
if (this.compareTo(a) >= 0) {
it1 = first.listIterator(size1);
it2 = second.listIterator(size2);
} else {
it2 = first.listIterator(size1);
it1 = second.listIterator(size2);
}
boolean riporto = false;
while(it1.hasPrevious()) {
Integer current1 = it1.previous();
Integer current2 = (it2.hasPrevious()) ? it2.previous() : 0;
int sum = current1 + current2;
if (riporto) {
sum++;
}
if (sum >= 10) { // aggiungere riporto al prossimo
sum -= 10;
riporto = true;
} else {
riporto = false;
}
ret.addFirst(sum);
}
if (riporto) {
ret.addFirst(1);
}
return new BigIntLL(ret);
}
/**
* dato un BigInt restituisce l'ipotetica LinkedList corrispondente,
* utilizzabile solo all'interno dell'implementazione BigIntLL
* @param a BigInt da cui ricavare le cifre
* @returns LinkedList con le cifre del BigInt come elementi
*/
private LinkedList<Integer> bigIntToLL(BigInt a) {
LinkedList<Integer> ret = new LinkedList<>();
String s = a.value();
for (int i = 0; i < s.length(); i++) {
ret.addLast(
Integer.parseInt(
Character.toString(
s.charAt(i)
)));
}
return ret;
}
/**
* implementazione custom di Comparable per i BigInt
* verifica prima la lunghezza, a parità di lunghezza verifica il valore delle cifre
* dalla più significativa alla meno significativa
* @returns intero maggiore di 0 se this > o, intero minore di 0 se this < 0, 0 se this = o
*/
@Override
public int compareTo(BigInt o) {
if (this.length() > o.length()) return 1;
if (this.length() < o.length()) return -1;
Iterator<Integer> it1 = this.iterator();
Iterator<Integer> it2 = o.iterator();
for (; it1.hasNext() && it2.hasNext() ;) {
Integer i1 = it1.next();
Integer i2 = it2.next();
if (i1 != i2) return i1 - i2;
}
return 0;
}
@Override
public Iterator<Integer> iterator() {
return bigInt.iterator();
}
}