+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
1/** 2* Licensed to the Apache Software Foundation (ASF) under one 3* or more contributor license agreements. See the NOTICE file 4* distributed with this work for additional information 5* regarding copyright ownership. The ASF licenses this file 6* to you under the Apache License, Version 2.0 (the 7* "License"); you may not use this file except in compliance 8* with the License. You may obtain a copy of the License at 9* 10* http://www.apache.org/licenses/LICENSE-2.0 11* 12* Unless required by applicable law or agreed to in writing, software 13* distributed under the License is distributed on an "AS IS" BASIS, 14* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15* See the License for the specific language governing permissions and 16* limitations under the License. 17*/ 18package org .apache .hadoop .examples .dancing ; 19 20import java .util .*; 21 22import org .apache .commons .logging .Log ; 23import org .apache .commons .logging .LogFactory ; 24 25/** 26* A generic solver for tile laying problems using Knuth's dancing link 27* algorithm. It provides a very fast backtracking data structure for problems 28* that can expressed as a sparse boolean matrix where the goal is to select a 29* subset of the rows such that each column has exactly 1 true in it. 30* 31* The application gives each column a name and each row is named after the 32* set of columns that it has as true. Solutions are passed back by giving the 33* selected rows' names. 34* 35* The type parameter ColumnName is the class of application's column names. 36*/ 37public class DancingLinks <ColumnName > { 38private static final Log LOG = 39LogFactory .getLog (DancingLinks .class .getName ()); 40 41/** 42* A cell in the table with up/down and left/right links that form doubly 43* linked lists in both directions. It also includes a link to the column 44* head. 45*/ 46private static class Node <ColumnName > { 47Node <ColumnName >left ; 48Node <ColumnName >right ; 49Node <ColumnName >up ; 50Node <ColumnName >down ; 51ColumnHeader <ColumnName >head ; 52 53Node (Node <ColumnName >l ,Node <ColumnName >r ,Node <ColumnName >u , 54Node <ColumnName >d ,ColumnHeader <ColumnName >h ) { 55left =l ; 56right =r ; 57up =u ; 58down =d ; 59head =h ; 60 } 61 62Node () { 63this (null ,null ,null ,null ,null ); 64 } 65 } 66 67/** 68* Column headers record the name of the column and the number of rows that 69* satisfy this column. The names are provided by the application and can 70* be anything. The size is used for the heuristic for picking the next 71* column to explore. 72*/ 73private static class ColumnHeader <ColumnName >extends Node <ColumnName > { 74ColumnName name ; 75int size ; 76 77ColumnHeader (ColumnName n ,int s ) { 78name =n ; 79size =s ; 80head =this ; 81 } 82 83ColumnHeader () { 84this (null ,0 ); 85 } 86 } 87 88/** 89* The head of the table. Left/Right from the head are the unsatisfied 90* ColumnHeader objects. 91*/ 92private ColumnHeader <ColumnName >head ; 93 94/** 95* The complete list of columns. 96*/ 97private List <ColumnHeader <ColumnName >>columns ; 98 99public DancingLinks () { 100head =new ColumnHeader <ColumnName >(null ,0 ); 101head .left =head ; 102head .right =head ; 103head .up =head ; 104head .down =head ; 105columns =new ArrayList <ColumnHeader <ColumnName >>(200 ); 106 } 107 108/** 109* Add a column to the table 110* @param name The name of the column, which will be returned as part of 111* solutions 112* @param primary Is the column required for a solution? 113*/ 114public void addColumn (ColumnName name ,boolean primary ) { 115ColumnHeader <ColumnName >top =new ColumnHeader <ColumnName >(name ,0 ); 116top .up =top ; 117top .down =top ; 118if (primary ) { 119Node <ColumnName >tail =head .left ; 120tail .right =top ; 121top .left =tail ; 122top .right =head ; 123head .left =top ; 124 }else { 125top .left =top ; 126top .right =top ; 127 } 128columns .add (top ); 129 } 130 131/** 132* Add a column to the table 133* @param name The name of the column, which will be included in the solution 134*/ 135public void addColumn (ColumnName name ) { 136addColumn (name ,true ); 137 } 138 139/** 140* Get the number of columns. 141* @return the number of columns 142*/ 143public int getNumberColumns () { 144return columns .size (); 145 } 146 147/** 148* Get the name of a given column as a string 149* @param index the index of the column 150* @return a string representation of the name 151*/ 152public String getColumnName (int index ) { 153return columns .get (index ).name .toString (); 154 } 155 156/** 157* Add a row to the table. 158* @param values the columns that are satisfied by this row 159*/ 160public void addRow (boolean []values ) { 161Node <ColumnName >prev =null ; 162for (int i =0 ;i <values .length ; ++i ) { 163if (values [i ]) { 164ColumnHeader <ColumnName >top =columns .get (i ); 165top .size +=1 ; 166Node <ColumnName >bottom =top .up ; 167Node <ColumnName >node =new Node <ColumnName >(null ,null ,bottom , 168top ,top ); 169bottom .down =node ; 170top .up =node ; 171if (prev !=null ) { 172Node <ColumnName >front =prev .right ; 173node .left =prev ; 174node .right =front ; 175prev .right =node ; 176front .left =node ; 177 }else { 178node .left =node ; 179node .right =node ; 180 } 181prev =node ; 182 } 183 } 184 } 185 186/** 187* Applications should implement this to receive the solutions to their 188* problems. 189*/ 190public interface SolutionAcceptor <ColumnName > { 191/** 192* A callback to return a solution to the application. 193* @param value a List of List of ColumnNames that were satisfied by each 194* selected row 195*/ 196void solution (List <List <ColumnName >>value ); 197 } 198 199/** 200* Find the column with the fewest choices. 201* @return The column header 202*/ 203private ColumnHeader <ColumnName >findBestColumn () { 204int lowSize =Integer .MAX_VALUE ; 205ColumnHeader <ColumnName >result =null ; 206ColumnHeader <ColumnName >current = (ColumnHeader <ColumnName >)head .right ; 207while (current !=head ) { 208if (current .size <lowSize ) { 209lowSize =current .size ; 210result =current ; 211 } 212current = (ColumnHeader <ColumnName >)current .right ; 213 } 214return result ; 215 } 216 217/** 218* Hide a column in the table 219* @param col the column to hide 220*/ 221private void coverColumn (ColumnHeader <ColumnName >col ) { 222LOG .debug ("cover " +col .head .name ); 223// remove the column 224col .right .left =col .left ; 225col .left .right =col .right ; 226Node <ColumnName >row =col .down ; 227while (row !=col ) { 228Node <ColumnName >node =row .right ; 229while (node !=row ) { 230node .down .up =node .up ; 231node .up .down =node .down ; 232node .head .size -=1 ; 233node =node .right ; 234 } 235row =row .down ; 236 } 237 } 238 239/** 240* Uncover a column that was hidden. 241* @param col the column to unhide 242*/ 243private void uncoverColumn (ColumnHeader <ColumnName >col ) { 244LOG .debug ("uncover " +col .head .name ); 245Node <ColumnName >row =col .up ; 246while (row !=col ) { 247Node <ColumnName >node =row .left ; 248while (node !=row ) { 249node .head .size +=1 ; 250node .down .up =node ; 251node .up .down =node ; 252node =node .left ; 253 } 254row =row .up ; 255 } 256col .right .left =col ; 257col .left .right =col ; 258 } 259 260/** 261* Get the name of a row by getting the list of column names that it 262* satisfies. 263* @param row the row to make a name for 264* @return the list of column names 265*/ 266private List <ColumnName >getRowName (Node <ColumnName >row ) { 267List <ColumnName >result =new ArrayList <ColumnName >(); 268result .add (row .head .name ); 269Node <ColumnName >node =row .right ; 270while (node !=row ) { 271result .add (node .head .name ); 272node =node .right ; 273 } 274return result ; 275 } 276 277/** 278* Find a solution to the problem. 279* @param partial a temporary datastructure to keep the current partial 280* answer in 281* @param output the acceptor for the results that are found 282* @return the number of solutions found 283*/ 284private int search (List <Node <ColumnName >>partial ,SolutionAcceptor <ColumnName >output ) { 285int results =0 ; 286if (head .right ==head ) { 287List <List <ColumnName >>result =new ArrayList <List <ColumnName >>(partial .size ()); 288for (Node <ColumnName >row :partial ) { 289result .add (getRowName (row )); 290 } 291output .solution (result ); 292results +=1 ; 293 }else { 294ColumnHeader <ColumnName >col =findBestColumn (); 295if (col .size >0 ) { 296coverColumn (col ); 297Node <ColumnName >row =col .down ; 298while (row !=col ) { 299partial .add (row ); 300Node <ColumnName >node =row .right ; 301while (node !=row ) { 302coverColumn (node .head ); 303node =node .right ; 304 } 305results +=search (partial ,output ); 306partial .remove (partial .size () -1 ); 307node =row .left ; 308while (node !=row ) { 309uncoverColumn (node .head ); 310node =node .left ; 311 } 312row =row .down ; 313 } 314uncoverColumn (col ); 315 } 316 } 317return results ; 318 } 319 320/** 321* Generate a list of prefixes down to a given depth. Assumes that the 322* problem is always deeper than depth. 323* @param depth the depth to explore down 324* @param choices an array of length depth to describe a prefix 325* @param prefixes a working datastructure 326*/ 327private void searchPrefixes (int depth ,int []choices , 328List <int []>prefixes ) { 329if (depth ==0 ) { 330prefixes .add (choices .clone ()); 331 }else { 332ColumnHeader <ColumnName >col =findBestColumn (); 333if (col .size >0 ) { 334coverColumn (col ); 335Node <ColumnName >row =col .down ; 336int rowId =0 ; 337while (row !=col ) { 338Node <ColumnName >node =row .right ; 339while (node !=row ) { 340coverColumn (node .head ); 341node =node .right ; 342 } 343choices [choices .length -depth ] =rowId ; 344searchPrefixes (depth -1 ,choices ,prefixes ); 345node =row .left ; 346while (node !=row ) { 347uncoverColumn (node .head ); 348node =node .left ; 349 } 350row =row .down ; 351rowId +=1 ; 352 } 353uncoverColumn (col ); 354 } 355 } 356 } 357 358/** 359* Generate a list of row choices to cover the first moves. 360* @param depth the length of the prefixes to generate 361* @return a list of integer arrays that list the rows to pick in order 362*/ 363public List <int []>split (int depth ) { 364int []choices =new int [depth ]; 365List <int []>result =new ArrayList <int []>(100000 ); 366searchPrefixes (depth ,choices ,result ); 367return result ; 368 } 369 370/** 371* Make one move from a prefix 372* @param goalRow the row that should be choosen 373* @return the row that was found 374*/ 375private Node <ColumnName >advance (int goalRow ) { 376ColumnHeader <ColumnName >col =findBestColumn (); 377if (col .size >0 ) { 378coverColumn (col ); 379Node <ColumnName >row =col .down ; 380int id =0 ; 381while (row !=col ) { 382if (id ==goalRow ) { 383Node <ColumnName >node =row .right ; 384while (node !=row ) { 385coverColumn (node .head ); 386node =node .right ; 387 } 388return row ; 389 } 390id +=1 ; 391row =row .down ; 392 } 393 } 394return null ; 395 } 396 397/** 398* Undo a prefix exploration 399* @param row 400*/ 401private void rollback (Node <ColumnName >row ) { 402Node <ColumnName >node =row .left ; 403while (node !=row ) { 404uncoverColumn (node .head ); 405node =node .left ; 406 } 407uncoverColumn (row .head ); 408 } 409 410/** 411* Given a prefix, find solutions under it. 412* @param prefix a list of row choices that control which part of the search 413* tree to explore 414* @param output the output for each solution 415* @return the number of solutions 416*/ 417public int solve (int []prefix ,SolutionAcceptor <ColumnName >output ) { 418List <Node <ColumnName >>choices =new ArrayList <Node <ColumnName >>(); 419for (int i =0 ;i <prefix .length ; ++i ) { 420choices .add (advance (prefix [i ])); 421 } 422int result =search (choices ,output ); 423for (int i =prefix .length -1 ;i >=0 ; --i ) { 424rollback (choices .get (i )); 425 } 426return result ; 427 } 428 429/** 430* Solve a complete problem 431* @param output the acceptor to receive answers 432* @return the number of solutions 433*/ 434public int solve (SolutionAcceptor <ColumnName >output ) { 435return search (new ArrayList <Node <ColumnName >>(),output ); 436 } 437 438}