~slub.team/goobi-indexserver/3.x

//System.out.println(" cycle upto=" + upto + " arc.label=" + arc.label + " (" + (char) arc.label + ") targetLabel=" + targetLabel + " isLast?=" + arc.isLast());

277

278

if (arc.bytesPerArc != 0 && arc.label != FST.END_LABEL) {

279

// Arcs are fixed array -- use binary search to find

280

// the target.

281

282

final FST<T>.BytesReader in = fst.getBytesReader(0);

283

int low = arc.arcIdx;

284

int high = arc.numArcs-1;

285

int mid = 0;

286

//System.out.println("do arc array low=" + low + " high=" + high + " targetLabel=" + targetLabel);

287

boolean found = false;

288

while (low <= high) {

289

mid = (low + high) >>> 1;

290

in.pos = arc.posArcsStart - arc.bytesPerArc*mid - 1;

291

final int midLabel = fst.readLabel(in);

292

final int cmp = midLabel - targetLabel;

293

//System.out.println(" cycle low=" + low + " high=" + high + " mid=" + mid + " midLabel=" + midLabel + " cmp=" + cmp);

294

if (cmp < 0)

295

low = mid + 1;

296

else if (cmp > 0)

297

high = mid - 1;

298

else {

299

found = true;

300

break;

301

}

302

}

303

304

// NOTE: this code is dup'd w/ the code below (in

305

// the outer else clause):

306

if (found) {

307

// Match -- recurse

308

//System.out.println(" match! arcIdx=" + mid);

309

arc.arcIdx = mid-1;

310

fst.readNextRealArc(arc, in);

311

assert arc.arcIdx == mid;

312

assert arc.label == targetLabel: "arc.label=" + arc.label + " vs targetLabel=" + targetLabel + " mid=" + mid;

313

output[upto] = fst.outputs.add(output[upto-1], arc.output);

314

if (targetLabel == FST.END_LABEL) {

315

return;

316

}

317

setCurrentLabel(arc.label);

318

incr();

319

arc = fst.readFirstTargetArc(arc, getArc(upto));

320

targetLabel = getTargetLabel();

321

continue;

322

} else if (high == -1) {

323

//System.out.println(" before first");

324

// Very first arc is after our target

325

// TODO: if each arc could somehow read the arc just

326

// before, we can save this re-scan. The ceil case

327

// doesn't need this because it reads the next arc

328

// instead:

329

while(true) {

330

// First, walk backwards until we find a first arc

331

// that's before our target label:

332

fst.readFirstTargetArc(getArc(upto-1), arc);

333

if (arc.label < targetLabel) {

334

// Then, scan forwards to the arc just before

335

// the targetLabel:

336

while(!arc.isLast() && fst.readNextArcLabel(arc) < targetLabel) {

337

fst.readNextArc(arc);

338

}

339

pushLast();

340

return;

341

}

342

upto--;

343

if (upto == 0) {

344

return;

345

}

346

targetLabel = getTargetLabel();

347

arc = getArc(upto);

348

}

349

} else {

350

// There is a floor arc:

351

arc.arcIdx = (low > high ? high : low)-1;

352

//System.out.println(" hasFloor arcIdx=" + (arc.arcIdx+1));

353

fst.readNextRealArc(arc, in);

354

assert arc.isLast() || fst.readNextArcLabel(arc) > targetLabel;

355

assert arc.label < targetLabel;

356

pushLast();

357

return;

358

}

359

} else {

360

361

if (arc.label == targetLabel) {

362

// Match -- recurse

363

output[upto] = fst.outputs.add(output[upto-1], arc.output);

364

if (targetLabel == FST.END_LABEL) {

365

return;

366

}

367

setCurrentLabel(arc.label);

368

incr();

369

arc = fst.readFirstTargetArc(arc, getArc(upto));

370

targetLabel = getTargetLabel();

371

} else if (arc.label > targetLabel) {

372

// TODO: if each arc could somehow read the arc just

373

// before, we can save this re-scan. The ceil case

374

// doesn't need this because it reads the next arc

375

// instead:

376

while(true) {

377

// First, walk backwards until we find a first arc

378

// that's before our target label:

379

fst.readFirstTargetArc(getArc(upto-1), arc);

380

if (arc.label < targetLabel) {

381

// Then, scan forwards to the arc just before

382

// the targetLabel:

383

while(!arc.isLast() && fst.readNextArcLabel(arc) < targetLabel) {

384

fst.readNextArc(arc);

385

}

386

pushLast();

387

return;

388

}

389

upto--;

390

if (upto == 0) {

391

return;

392

}

393

targetLabel = getTargetLabel();

394

arc = getArc(upto);

395

}

396

} else if (!arc.isLast()) {

397

//System.out.println(" check next label=" + fst.readNextArcLabel(arc) + " (" + (char) fst.readNextArcLabel(arc) + ")");

398

if (fst.readNextArcLabel(arc) > targetLabel) {

399

pushLast();

400

return;

401

} else {

402

// keep scanning

403

fst.readNextArc(arc);

404

}

405

} else {

406

pushLast();

407

return;

408

}

409

}

410

}

411

}

412

413

private void incr() {

414

upto++;

415

grow();

416

if (arcs.length <= upto) {

417

@SuppressWarnings("unchecked") final FST.Arc<T>[] newArcs =

418

new FST.Arc[ArrayUtil.oversize(1+upto, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];

419

System.arraycopy(arcs, 0, newArcs, 0, arcs.length);

420

arcs = newArcs;

421

}

422

if (output.length <= upto) {

423

@SuppressWarnings("unchecked") final T[] newOutput =

424

(T[]) new Object[ArrayUtil.oversize(1+upto, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];

425

System.arraycopy(output, 0, newOutput, 0, output.length);

426

output = newOutput;

427

}

428

}

429

430

// Appends current arc, and then recurses from its target,

431

// appending first arc all the way to the final node

432

private void pushFirst() throws IOException {

433

434

FST.Arc<T> arc = arcs[upto];

435

assert arc != null;

436

437

while (true) {

438

output[upto] = fst.outputs.add(output[upto-1], arc.output);

439

if (arc.label == FST.END_LABEL) {

440

// Final node

441

break;

442

}

443

//System.out.println(" pushFirst label=" + (char) arc.label + " upto=" + upto + " output=" + fst.outputs.outputToString(output[upto]));

444

setCurrentLabel(arc.label);

445

incr();

446

447

final FST.Arc<T> nextArc = getArc(upto);

448

fst.readFirstTargetArc(arc, nextArc);

449

arc = nextArc;

450

}

451

}

452

453

// Recurses from current arc, appending last arc all the

454

// way to the first final node

455

private void pushLast() throws IOException {

456

457

FST.Arc<T> arc = arcs[upto];

458

assert arc != null;

459

460

while (true) {

461

setCurrentLabel(arc.label);

462

output[upto] = fst.outputs.add(output[upto-1], arc.output);

463

if (arc.label == FST.END_LABEL) {

464

// Final node

465

break;

466

}

467

incr();

468

469

arc = fst.readLastTargetArc(arc, getArc(upto));

470

}

471

}

472

473

private FST.Arc<T> getArc(int idx) {

474

if (arcs[idx] == null) {

475

arcs[idx] = new FST.Arc<T>();

476

}

477

return arcs[idx];

478

}

479

}

Older »