1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
2 * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
3 * http://www.gnu.org/software/gnugo/ for more information. *
4 * *
5 * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
6 * 2008 and 2009 by the Free Software Foundation. *
7 * *
8 * This program is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU General Public License as *
10 * published by the Free Software Foundation - version 3 or *
11 * (at your option) any later version. *
12 * *
13 * This program is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16 * GNU General Public License in file COPYING for more details. *
17 * *
18 * You should have received a copy of the GNU General Public *
19 * License along with this program; if not, write to the Free *
20 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
21 * Boston, MA 02111, USA. *
22 \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
23
24 #include "gnugo.h"
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "liberty.h"
31
32
33 static void movelist_sort_points(int max_points, int points[], int codes[]);
34 static void swap_points_and_codes(int points[], int codes[], int m, int n);
35
36
37 /* Return the code for the move if it is known.
38 */
39 int
movelist_move_known(int move,int max_points,int points[],int codes[])40 movelist_move_known(int move, int max_points, int points[], int codes[])
41 {
42 int k;
43
44 for (k = 0; k < max_points; k++) {
45 if (codes[k] == 0)
46 return 0;
47 if (points[k] == move)
48 return codes[k];
49 }
50 return 0;
51 }
52
53
54 /*
55 * This function does the real work for change_attack(),
56 * change_defense(), change_attack_threat(), and
57 * change_defense_threat().
58 */
59
60 void
movelist_change_point(int move,int code,int max_points,int points[],int codes[])61 movelist_change_point(int move, int code, int max_points,
62 int points[], int codes[])
63 {
64 int k;
65
66 /* First see if we already know about this point. */
67 for (k = 0; k < max_points; k++)
68 if (points[k] == move)
69 break;
70
71 /* Yes, we do. */
72 if (k < max_points) {
73 if (codes[k] <= code)
74 return; /* Old news. */
75
76 codes[k] = code;
77 movelist_sort_points(max_points, points, codes);
78 return;
79 }
80
81 /* This tactical point is new to us. */
82 if (code > codes[max_points - 1]) {
83 points[max_points - 1] = move;
84 codes[max_points - 1] = code;
85 movelist_sort_points(max_points, points, codes);
86 }
87 }
88
89
90 /* Sort the tactical points so we have it sorted in falling order on
91 * the code values.
92 *
93 * We use shaker sort because we prefer a stable sort and in all use
94 * cases we can expect it to suffice with one turn through the outer
95 * loop.
96 */
97
98 static void
movelist_sort_points(int max_points,int points[],int codes[])99 movelist_sort_points(int max_points, int points[], int codes[])
100 {
101 int start = 0;
102 int end = max_points - 1;
103 int new_start;
104 int new_end;
105 int k;
106
107 while (start < end) {
108 new_start = end;
109 for (k = end; k > start; k--)
110 if (codes[k] > codes[k-1]) {
111 swap_points_and_codes(points, codes, k, k-1);
112 new_start = k;
113 }
114 start = new_start;
115 new_end = start;
116 for (k = start; k < end - 1; k++)
117 if (codes[k] < codes[k+1]) {
118 swap_points_and_codes(points, codes, k, k+1);
119 new_end = k;
120 }
121 end = new_end;
122 }
123 }
124
125 static void
swap_points_and_codes(int points[],int codes[],int m,int n)126 swap_points_and_codes(int points[], int codes[], int m, int n)
127 {
128 int tmp = points[m];
129 points[m] = points[n];
130 points[n] = tmp;
131 tmp = codes[m];
132 codes[m] = codes[n];
133 codes[n] = tmp;
134 }
135
136
137
138 /*
139 * Local Variables:
140 * tab-width: 8
141 * c-basic-offset: 2
142 * End:
143 */
144