import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * @author Christopher Manning */ public class Or { /** If true, loaded postings lists are printed; this just shows that they were loaded correctly. */ static boolean DEBUG = false; /** Test cases */ static final String[][] mergeTestCases = { { "1; 2; 4; 5; 7; 13", "1; 4; 5; 6; 8; 10; 13", "[1, 2, 4, 5, 6, 7, 8, 10, 13]" }, { "1; 5", "1; 5", "[1, 5]" }, { "1", "1", "[1]" }, { "1; 17; 21", "4; 5; 17; 21; 97; 108", "[1, 4, 5, 17, 21, 97, 108]" }, { "5; 11; 12; 14; 15; 103", "3; 8; 11; 14; 15; 16; 18; 100; 103; 109", "[3, 5, 8, 11, 12, 14, 15, 16, 18, 100, 103, 109]" }, { "1; 5; 11; 13; 19; 43", "2; 3; 5; 9; 11; 15; 19; 33; 45", "[1, 2, 3, 5, 9, 11, 13, 15, 19, 33, 43, 45]" }, { "1", "2; 189", "[1, 2, 189]" }, { "3;4;9;16;19;24;25;27;28;30;31;32;33;35;36;43;46;47;52;55;57;60;61;62;" + "64;65;66;77;78;80;83;86;91;98;99;100;101;102;103;104;106;108;112;113;116;" + "117;119;120;127;141;147;151;156;158;168;170;172;175;179;182;184;185;187;195;" + "197;199;202;206;207;208;209;210;213;221;225;227;228;233;238;249;252;255;256;" + "266;267;268;270;271;273;274;281;284;285;289;290;292;294;299;301;302;303;306;" + "308;312;320;321;322;325;326;328;329;332;334;335;337;341;342;344;345;347;349;" + "356;357;358;360;364;376;377;379;382;383;385;395;397;403;404;405;406;410;412;" + "417;418;423;430;431;432;433;434;437;440;441;445;446;452;453;454;461;464;466;" + "469;477;480;486;487;488;495;496;506;507;511;512;517;518;520;522;524;526;532;" + "535;540;543;549;550;558;562;563;564;571;574;581;586;587;592;597;598;604;607;" + "608;615;620;621;622;625;633;634;635;636;639;640;642;653;654;656;658;660;668;" + "671;676;680;681;683;686;687;689;694;697;702;703;708;710;711;714;722;723;729;" + "730;737;739;742;746;747;750;756;757;758;759;764;765;766;769;770;772;777;780;" + "782;783;784;791;795;798;801;807;812;815;816;822;823;824;825;828;830;833;835;" + "836;837;841;852;854;863;864;865;868;870;873;880;882;884;887;888;889;897;902;" + "906;912;914;918;922;924;925;928;929;932;933;934;938;939;941;943;944;947;948;" + "952;955;961;962;963;968;971;973;975;979;980;983;984;987;989;993;995;996;" + "999", // "faculty" in first 1000 documents of Stanford crawl "324;335;418;466;505;686", // "anthropology" in first 1000 documents of Stanford crawl "[3, 4, 9, 16, 19, 24, 25, 27, 28, 30, 31, 32, 33, 35, 36, 43, 46, 47, 52, 55, 57, 60, " + "61, 62, 64, 65, 66, 77, 78, 80, 83, 86, 91, 98, 99, 100, 101, 102, 103, 104, " + "106, 108, 112, 113, 116, 117, 119, 120, 127, 141, 147, 151, 156, 158, 168, 170, " + "172, 175, 179, 182, 184, 185, 187, 195, 197, 199, 202, 206, 207, 208, 209, 210, " + "213, 221, 225, 227, 228, 233, 238, 249, 252, 255, 256, 266, 267, 268, 270, 271, " + "273, 274, 281, 284, 285, 289, 290, 292, 294, 299, 301, 302, 303, 306, 308, 312, " + "320, 321, 322, 324, 325, 326, 328, 329, 332, 334, 335, 337, 341, 342, 344, 345, " + "347, 349, 356, 357, 358, 360, 364, 376, 377, 379, 382, 383, 385, 395, 397, 403, " + "404, 405, 406, 410, 412, 417, 418, 423, 430, 431, 432, 433, 434, 437, 440, 441, " + "445, 446, 452, 453, 454, 461, 464, 466, 469, 477, 480, 486, 487, 488, 495, 496, " + "505, 506, 507, 511, 512, 517, 518, 520, 522, 524, 526, 532, 535, 540, 543, 549, " + "550, 558, 562, 563, 564, 571, 574, 581, 586, 587, 592, 597, 598, 604, 607, 608, " + "615, 620, 621, 622, 625, 633, 634, 635, 636, 639, 640, 642, 653, 654, 656, 658, " + "660, 668, 671, 676, 680, 681, 683, 686, 687, 689, 694, 697, 702, 703, 708, 710, " + "711, 714, 722, 723, 729, 730, 737, 739, 742, 746, 747, 750, 756, 757, 758, 759, " + "764, 765, 766, 769, 770, 772, 777, 780, 782, 783, 784, 791, 795, 798, 801, 807, " + "812, 815, 816, 822, 823, 824, 825, 828, 830, 833, 835, 836, 837, 841, 852, 854, " + "863, 864, 865, 868, 870, 873, 880, 882, 884, 887, 888, 889, 897, 902, 906, 912, " + "914, 918, 922, 924, 925, 928, 929, 932, 933, 934, 938, 939, 941, 943, 944, 947, " + "948, 952, 955, 961, 962, 963, 968, 971, 973, 975, 979, 980, 983, 984, 987, 989, " + "993, 995, 996, 999]" }, }; /** Stores the Posting for a single document: a docID and optionally a list of document positions. */ private static class Posting { final int docID; final List positions; public Posting(int docID, List positions) { this.docID = docID; this.positions = positions; } public Iterator positions() { return positions.iterator(); } public String toString() { return docID + ":" + positions; } } /** Returns the next item from the Iterator, or null if it is exhausted. * (This is a more C-like method than idiomatic Java, but we use it so as * to be more parallel to the pseudo-code in the textbook.) */ static X popNextOrNull(Iterator p) { if (p.hasNext()) { return p.next(); } else { return null; } } static List merge(Iterator p1, Iterator p2) { List answer = new ArrayList<>(); Posting pp1 = popNextOrNull(p1); Posting pp2 = popNextOrNull(p2); // WRITE ALGORITHM HERE return answer; } /** Load a single postings list: Information about where a single token * appears in documents in the collection. This can load either a document * level posting which is a list of integer docID separated by semicolons * or a positional postings list, where each docID is followed by a colon * and then * @param postingsString A String representation of a postings list * @return An Iterator over a {@code List} */ static Iterator loadPostingsList(String postingsString) { List postingsList = new ArrayList<>(); String[] postingsArray = postingsString.split(";"); for (String posting : postingsArray) { String[] bits = posting.split(":"); String[] poses = {}; if (bits.length > 1) { poses = bits[1].split(","); } int docID = Integer.valueOf(bits[0].trim()); List positions = new ArrayList<>(); for (String pos : poses) { positions.add(Integer.valueOf(pos.trim())); } Posting post = new Posting(docID, positions); postingsList.add(post); } if (DEBUG) { System.err.println("Loaded postings list: " + postingsList); } return postingsList.iterator(); } /** Main method. With no parameters, it runs some internal test cases. * With two postings list arguments, it or's the arguments given on the command line. * Otherwise, it will print a usage message. * * @param args Command-line arguments, as above. */ public static void main(String[] args) { if (args.length == 0) { for (String[] test : mergeTestCases) { Iterator pl1 = loadPostingsList(test[0]); Iterator pl2 = loadPostingsList(test[1]); System.out.println("Merge of " + test[0]); System.out.println(" and " + test[1] + ": "); List ans = merge(pl1, pl2); System.out.println("Answer: " + ans); if ( ! ans.toString().equals(test[2])) { System.out.println("Correct: " + test[2]); System.out.println("*** ERROR ***"); } System.out.println(); } } else if (args.length != 2) { System.err.println("Usage: java Or postingsList1 postingsList2"); System.err.println(" postingsList format(s): '1:17,25; 4:17,191,291,430,434; 5:14,19,10'"); System.err.println(" or: '1; 4; 5'"); } else { Iterator pl1 = loadPostingsList(args[0]); Iterator pl2 = loadPostingsList(args[1]); List ans = merge(pl1, pl2); System.out.println(ans); } } }